I was intrigued when I read about sort()'s inefficiency in IE
at Web Reflection. I decided to investigate it myself.
Number of comparisons for an array of 1,000 elements:
| Browser | Same | Asc | Desc | Random |
|---|---|---|---|---|
| Chrome 2 | 0 | 9,941 | 10,147 | 10,905 |
| FireFox 3 | 999 | 999 | 5,681 | 9,009 |
| IE 7 | 17,583 | 17,583 | 15,965 | 16,860 |
| Opera 9.6 | 499,485 | 7,498 | 8,550 | 12,353 |
| Safari 4 | 8,977 | 8,977 | 8,977 | 8,775 |
| Your browser |
Figures in italic means they vary per-run.
We expect an average of O(n log2 n) comparisons — around 9,966 — so the results are pretty good, except for one.
The worst case is O(n2), which is what we see for Opera: 1,000 + 999 + 998 + ... = 1/2 * 1,000 * 999 = 499,500. It's not exact, but it's in the ballpark.
How does Chrome know the array has the same elements without calling the
comparator? Good question! Apparently it can handle basic types. Changing the
element to {} yields a count of 999.
FireFox checks if the array is already sorted. It handles the same/ascending-elements case properly, but why doesn't it handle the descending-elements case?
Opera handles the same-elements case very poorly. It should stop and check the array if it receives the same comparison result after going through the first 20% of the array. Something may be amiss.
Note: invalid controls are disabled. FireFox, IE and Safari do not update the array on the fly. Chrome and Opera do.
(I'm assuming sort() does not move the elements unnecessarily,
which is not always true. If this is false, then only the same-elements array
will show the current array state properly.)
On some browsers, the array will not look sorted, but it is! This is
because sort() has enough information to do the final sort
without calling the comparator.
Opera and Chrome are using Quick Sort. That's no surprise as it is the best general-purpose sorting algo. Chrome seems to be using 3-way partitioning, whereas Opera is using a standard textbook implementation.
Judging by how the comparisions are made, FireFox seems to be using Merge Sort.
Based on the comparisons and run-time performance, I guess that Safari is using Heap Sort.
I have no idea what sorting algo IE is using. It looks heap/tree related.
There are many general-purpose sorting algo. The ones that I know: Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Shell Sort, Merge Sort, Quick Sort and Radix Sort (not fully general-purpose).
I've only seen Insertion Sort, Merge Sort, Quick Sort and very rarely, Radix Sort, in the real world.
Insertion sort is very easy to implement. It is the fastest of the slow sorts, and speed does not matter if the array is small. Because insertion sort works very well for nearly-sorted data, many partition-based sorting algos switch to it when their working set is small.
Surprisingly, Merge sort is used by Perl and Java Run-Time's sorting functionality.
Quick sort is usually the programming language framework's default sorting functionality.
Radix sort is incredibly fast. However, it can only be used with keys composed of digits in lexicographic order.
I wonder if I'll ever see Shell Sort, my favourite sorting algo.