// For numeric comparison, which is fast, qsort is faster than mergesort. We
// also don't require mergesort's stability, since there's no user visible
// side-effect from swapping the order of equal primitive values.I am not arguing selection sort is a good sort for the reason chosen, but I will maintain that the real (yes: "real", that is the correct term to use here) sorting algorithm used by WebKit for "JS arrays" (remember: I was complaining about "how incorrect this submission is") is actually a choice between mergesort, quicksort, and an AVL tree.
Now, if the submission title had been "WebKit sorts sparse JS arrays using selection sort" or even "WebKit sorts non-standard JS arrays using selection sort" (to evoke the wording of the commit message 7 months ago), that would be different: that would not be a linkbait title. I could even maybe get behind "WebKit uses four different sorting algorithms, and one of them is selection sort?!".
However, when one sees the title "WebKit sorts JS arrays using Selection Sort", I think many, if not most, reasonable developers go "oh, wow, maybe I should be avoiding the WebKit sort algorithm, given that my arrays are reasonably sized... I wonder if they'll get that fixed"; but, when you click through to the actual code and read it you realize this would be wrong.
So, from my perspective, you are now arguing a strawman, and are doing so fairly abrasively :(. To be clear: I certainly am not defending the existence of selection sort in the codebase, even for non-standard arrays. That does not make this submission correct, or even reasonable: it is looking at the wrong code and making it out to be something it is not (even quite generally, "important").
Regardless, I got curious, and decided to look more into that sorting code. It is apparently sufficiently old that it predates WebKit being called "WebKit", so I went back through kdelibs and found the original commit that added it, from January 2001. At this time, most of the array implementation was still "does nothing, needs to be implemented" or "does the wrong thing, needs to be fixed".
http://quickgit.kde.org/index.php?p=kdelibs.git&a=commit...
It was in March of 2003, during a commit-spree of merging from Safari back to kjs, that the quick sort implementation and code to use it for JS arrays was added. This means that this submission's title was correct for two years, incorrect for almost 9 years, and then maybe-sort-of-almost-correct for 7 months.
Chrome uses quicksort + insertion sort, as mentioned in another comment. Firefox uses merge sort + insertion sort (https://mxr.mozilla.org/mozilla-central/source/js/src/jsarra...).
As a side note, Firefox's sort implementation slows down drastically when you use a custom comparison function because it has to call from C++ back out to JS (https://bugzilla.mozilla.org/show_bug.cgi?id=715181). Chrome's sort is presumably implemented in JS for this reason.
EDIT: Sparse mode is when JSC::JSArray switches from storing the array data as a vector to storing it in a map. You can see from the code at http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/r... that a vector will be used for sufficiently small arrays (< 10,000 elements) and for larger arrays that are at least 12.5% full.
No, O(N^2) sorting algorithms are just dumb in library/runtime[1] code. No one expects that, it will eventually bite anyone who uses the code. And this code is a booby trap, no one even knows if they're using it!
[1] In application code, where you might know a priori that they'll never sort more than "one screen worth" of data, I can see it being a reasonable hack. But never as part of a standard feature called "sort".
I'm not sure what sparse mode is, but let's try my Raymond Chen inspired psychic powers: if you assign a[0]=1 and a[1000000]=2, you don't want a 1 to 999999 to be stored, so an array like that will end up in a sparse mode which functions more like a hash table keyed by integers.
The same applies to non-arrays: since they aren't true arrays, they won't be stored in the blessed, contiguous way that the sort routine is expecting, so a slower access method has to be used.
Now, fast sorting is presumably written assuming the array is in a contiguous array. Since in sparse mode the array isn't like that, we aren't on the fast path, so it doesn't matter if we are slow, and correctness and special cases are more important, hence the simple selection sort algorithm.
Note also that line 633, 635 and 637 further specialise the fast path into three cases: a default sort with no user-defined comparator, a sort based on a built-in numerical comparator, and a more general sort using a user-defined comparator. (EDIT: The functions called on 633, 635 and 637 are defined in http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/r... from line 1409 onwards, and use quicksort or mergesort, except in the general case which uses an AVL tree, which feels odd but I'm sure there was a reason.)
TL;DR: This only applies to certain arrays; the performance is generally fine else someone would have noticed by now; if you are sorting array-like things or sparse arrays regularly, profile to discover if this is a problem for you.