الگوریتم مرتب سازی شمارشی:

 1-11شکل

به هر حال برای K های کمتر حد پایین دیگری فرض می کنیم. برای مثال هنگامی که K=1 می توان الگوریتمی از مرتبه O(log N) داشت. در این حالت مسئله تبدیل به مسئله مرتب سازی در یک درخت باینری با پردازنده های بیتی است که ریشه شامل آرایه خطی  از N cell پردازنده بیتی است. و هر برگ شامل 1 یا 0 است. و جواب مورد انتظار این است که 0 ها در سمت چپ ترین برگها  و 1 ها در سمت راست ترین برگ ها قرار بگیرند. این کار در دو فاز انجام می شود. اول، m تعداد 1 ها در برگ ها را می شماریم . و سپس m برگ سمت راست را به 1 مقدار دهی و N-m برگ سمت راست را به 0 مقدار دهی می کنیم. 

اگر در هر گره درخت پردازنده لغتی داشته باشیم عملیات شمارش 1ها در برگ ها به سادگی امکان پذیر است. هر گره تعداد 1 ها در زیر درخت چپ و راستش را جمع می کند و ذخیره می کند.  مانند شکل زیر : 

شکل 1-12

اما اگر فقط پردازنده های بیتی در اختیار داشته باشیم مسئله کمی پیچیده تر خواهد شد. در حقیقت مسئله دقیقاً مسئله تیدیل یونری به باینری خواهد بود. که با استفاده از پایپلاین می توانیم مجموع اعداد را در 2lgN گام داشته باشیم. 

عمل پایه در هر پردازنده در شکل زیر نشان داده شده است. هر پردازنده یک حافظه داخلی 1 بیتی و 2 ورودی 1 بیتی و یک خروجی یک بیتی دارد. در هر گام پردازنده مجموع دو بیت ورودی و بیت ذخیره شده در حافظه اش را محاسبه می کند. حاصل یک عدد باینری 2 بیتی است. که بیت کم ارزش تر را به عنوان خروجی ارسال می کند و بیت پرارزش تر ( بیت نقلی ) را ذخیره می کند. در واقع هر پردازنده بعد از اینکه شروع به محاسبه می کند در iامین گام iامین بیت کم ارزش مجموع درختی که ریشه اش است را محاسبه می کند و iامین بیت نقلی را نیز دخیره می کند.

شکل 1-13

با اتصال 2N-2+lgN  عدد از این پردازنده ها می توان یک درخت ساخت. با N برگ. به وسیله استقرا می توان ثابت کرد که این درخت صحیح عمل می کند. اگر ورودی در هر برگ 1 بیتی باشد. 2lgN گام طول میکشد تا مجموع  در ریشه محاسبه شود. برای ظاهر شدن اولین عدد ( کم ارزش ترین بیت ) در خروجی lgN زمان لازم است و بعد از این در گام بیت بعدی ظاهر میشود که چون lg N بیت داریم می شود 2lgN.  شکل زیر نحوه انجام این مرحله ( محاسبه مجموع ) را نشان می دهد. 

شکل 1-14

بعد از محاسبه عدد m، تعداد 1 ها در برگ ها، تنها کار باقیمانده 1 کردن m برگ سمت راستی و 0 کردن N-m برگ سمت چپی است. اینکار نیز به سادگی در 2lgN گام قابل انجام است. نکته کلیدی استفاده از عدد N-m-1 و پیدا کردن این برگ ( با شمارش از سمت چپ ) و 1 کردن برگ های سمت راست این برگ و 0 کردن برگ های سمت چپ این برگ است. 

مسیر با شروع از ریشه و استفاده از بیت راهنما ( سمت چپ ترین بیت ) و انتخاب زیر درخت سمت چپ یا راست با استفاده از این بیت و سپس حذف این بیت پیدا می شود. در هر گام با استفاده از بیت راهنما زیر درخت را انتخاب و سپس بقیه بیت ها را به ریشه زیر درخت انتخاب شده می فرستیم و در صورتی که زیر درخت انتخابی زیر درخت سمت چپ باشد به برادر all 1 و در صورتی که زیر درخت انتخابی سمت راست باشد به برادر all 0 فرستاده می شود. این مرحله نیز در 2lg N گام به انجام می رسد. lg N گام برای ورود عدد ریشه و lg N گام دیگر برای رسیدن به برگ N-m-1 . مسیر به برگ به درستی با استفاده از آدرس دهی باینری که در اینجا استفاده شد پیدا می شود. نحوه استفاده از بیت راهنما بدین صورت است که در صورت 0 بودن این بیت زیر درخت سمت چپ انتخاب و all 1 به زیر درخت سمت راست فرستاده می شود و در صورت 1 بودن زیر درخت سمت راست انتخاب و all 0 به زیر درخت سمت چپ فرستاده می شود.

شکل 1-15

همین!