News for hackers. Stuff that matters.

A comment on WebKit sorts JS arrays using Selection Sort.

Re:WebKit sorts JS arrays using Selection Sort by mda on Friday July 13, 2012 @08:20AM (#4239472)
V8 sort algorithm (Quicksort + Insertion Sort):

http://code.google.com/p/v8/source/browse/trunk/src/array.js...

[ Parent | on HN ]
Re:WebKit sorts JS arrays using Selection Sort by maxpow4h on Friday July 13, 2012 @08:49AM (#4239568)
It's known as Introsort
[ Parent | on HN ]
Re:WebKit sorts JS arrays using Selection Sort by mda on Friday July 13, 2012 @09:56AM (#4239794)
No, Introsort is (Quicksort + Heapsort) designed to prevent algorithm to degenerate O(n^2) for particular input sets.

Afaik v8 (and Java's pre Java 7 versions) quicksort algorithms are based on Jon Bentley's work.

[ Parent | on HN ]