Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) is implemented as a 'tuned quicksort' rather than a radix sort.

I did a speed comparison a while ago, and with something like n>10000, radix sort was always faster. why?

share|improve this question

2 Answers 2

up vote 13 down vote accepted

I would speculate that:

  • Array.sort is implemented as quicksort, because quicksort can sort anything in decent time given a comparator.
  • Sorting a list of 10000 entries is not so common. Accessing a data-structure of 10000 or more elements is rather common. If you need to maintain order, a balanced search tree is often a better way to go than to sort your whole array every time you need the smallest element.
  • Sorting primitives is not so common, despite what university may teach.

The point is, it's not such a common use case, that it's optimization needs to be in the standard library. If you have written an application, that has performance issues, where you determine through profiling that sorting an array of 10000+ ints is actually the bottleneck, then you might as well write the sorting by hand or reconsider your choice of data structure in the first place.

share|improve this answer
    
Not 100% sure, but I think TimSort is used in some cases now. –  Martijn Verburg Feb 28 '12 at 20:50
    
But there is not something as Array.sort, there are multiple Array.sorts, and the question was about this specialized for numeric types ones. –  Donaudampfschifffreizeitfahrt Apr 19 '12 at 7:19

Back2dos has said it all, I will just try to further clarify the point which I think is the most important:

Radix sort can only sort the actual primitive values that are contained within the array, based on their binary digit patterns. In actual real-world software engineering scenarios, this case is encountered almost never. What we tend to do far more often is sort arrays of more complex (non-primitive) data structures, and some times we sort arrays of indexes to other entities.

Now, an array of indexes to other entities is in fact an array of primitives, but the sort order is provided by the comparator interface (and/or delegate in C#) which compares not the indexes, but the entities indexed by the indexes. Thus, the sort order bears absolutely no relationship to the order of the values of the primitives, and therefore radix sort is absolutely useless for this scenario.

An example:

We have an array of strings: [0]="Mike", [1]="Albert", [2]="Zoro". Then we declare an array of indexes to those strings: [0]=0, [1]=1, [2]=2. Then, we sort the array of indexes, passing it a comparator which compares not the indexes themselves, but the actual strings referred to by these indexes. After sorting, the resulting array of indexes will look like this: [0]=1, [1]=0, [2]=2. As you can see, this sort order has nothing to do with the binary patterns of the values contained within the array, and yet by traversing this array of indexes and fetching each corresponding string, we visit the strings in sorted order.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.