Re:WebKit sorts JS arrays using Selection Sort
by Nitramp on Friday July 13, 2012 @01:51PM
(#4240896)
Except that every sort algorithm in every library on earth falls back to selection sort (or similar) for small problems (e.g. N < 10), because that's more efficient than drilling a merge sort all the way down.
Re:WebKit sorts JS arrays using Selection Sort
by ajross on Friday July 13, 2012 @01:56PM
(#4240931)
How is that relevant? Is your contention that the code in question will never see performance problems because there's a constant factor that outweighs the runtime? That's not my read at all. It looks to me like sorting 40k items that happen to be packed in a sparse array is going to take on the order of a billion operations. No?
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".