How Does Your Browser Sort?

A look at sort()

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.

Questions

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.

How about a demo?


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.

Sorting Algo

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.

Other Sorting Algos

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.