Radix Sort
রেডিক্স সর্ট
Comparison ছাড়া key-এর digit ধরে digit stable sort করে integer বা fixed-length string sort — LSD থেকে MSD, মোট খরচ O(d·(n+k))।
also: radix sort, punch card sort
LSD (least significant digit first) পদ্ধতিতে প্রতিটা digit pass-এ counting sort চালে — তাই ভিত্তি sort-টা stable হতেই হবে, নাহলে আগের pass-এর সাজানো নষ্ট।
170, 90, 45, 75
pass 1 (units) : 170, 90, 45, 75
pass 2 (tens) : 45, 75, 170, 90
pass 3 (hundreds): 45, 75, 90, 170d digit, value range k হলে খরচ O(d·(n+k)) — comparison sort-এর n log n lower bound এখানে খাটে না, কারণ কোনো comparison-ই হয় না।
Trade-off: digit সংখ্যা d বড় হলে সুবিধা মিলিয়ে যায়, আর counting buffer লাগে।