When should we use Radix sort?

performance algorithm sorting quicksort radix-sort
Howard picture Howard · Nov 10, 2010 · Viewed 38.3k times · Source

It seems Radix sort has a very good average case performance, i.e. O(kN): http://en.wikipedia.org/wiki/Radix_sort

Yet it seems like most people are still using Quick Sort - why is this?

Answer

Mark Ransom picture Mark Ransom · Nov 10, 2010

Radix sort is harder to generalize than most other sorting algorithms. It requires fixed size keys, and some standard way of breaking the keys into pieces. Thus it never finds its way into libraries.

Related questions

Fast algorithm implementation to sort very small list

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the …

Read More
Fastest gap sequence for shell sort?

According to Marcin Ciura's Optimal (best known) sequence of increments for shell sort algorithm, the best sequence for shellsort is 1, 4, 10, 23, 57, 132, 301, 701..., but how can I generate such a sequence? In Marcin Ciura's paper, he said: Both Knuth’s and Hibbard’s …

Read More
What are the rules for the "Ω(n log n) barrier" for sorting algorithms?

I wrote a simple program that sorts in O(n). It is highly memory inefficient, but that's not the point. It uses the principle behind a HashMap for sorting: public class NLogNBreak { public static class LinkedListBack { public LinkedListBack(int val){ …

Read More