That was the fastest on my computer. It's surprisingly high, though. Maybe we should try experimenting on other setups.
On Tue, Sep 30, 2008 at 11:43 AM, Erik Corry <[EMAIL PROTECTED]> wrote: > > Why 22? > > On Tue, Sep 30, 2008 at 11:36 AM, <[EMAIL PROTECTED]> wrote: > > > > Reviewers: Christian Plesner Hansen, > > > > Description: > > Faster sort. > > > > Using insertion sort below a certain threshold to give faster sorting of > > arrays (esp. short ones). > > > > Please review this at http://codereview.chromium.org/6006 > > > > Affected files: > > M src/array.js > > > > > > Index: src/array.js > > =================================================================== > > --- src/array.js (revision 393) > > +++ src/array.js (working copy) > > @@ -648,6 +648,7 @@ > > > > function ArraySort(comparefn) { > > // In-place QuickSort algorithm. > > + // For short (length <= 22) arrays, insertion sort is used for > > efficiency. > > > > function Compare(x,y) { > > if (IS_UNDEFINED(x)) { > > @@ -668,8 +669,42 @@ > > else return x < y ? -1 : 1; > > }; > > > > + function InsertionSort(a, from, to) { > > + for(var i = from + 1; i < to; i++) { > > + var element = a[i]; > > + // place element in a[from..i[ > > + // binary search > > + var min = from; > > + var max = i; > > + while(min < max) { > > + var mid = min + ((max - min) >> 1); > > + var order = Compare(a[mid], element); > > + if (order == 0) { > > + min = max = mid; > > + break; > > + } > > + if (order < 0) { > > + min = mid + 1; > > + } else { > > + max = mid; > > + } > > + } > > + // place element at position min==max. > > + for(var j = min; j < i; j++) { > > + var tmp = a[j]; > > + a[j] = element; > > + element = tmp; > > + } > > + a[i] = element; > > + } > > + } > > + > > function QuickSort(a, from, to) { > > - if (from >= to - 1) return; > > + // Insertion sort is faster for short arrays. > > + if (to - from <= 22) { > > + InsertionSort(a, from, to); > > + return; > > + } > > var pivot_index = $floor($random() * (to - from)) + from; > > var pivot = a[pivot_index]; > > // Issue 95: Keep the pivot element out of the comparisons to avoid > > > > > > > > > > > > > > > -- > Erik Corry, Software Engineer > Google Denmark ApS. CVR nr. 28 86 69 84 > c/o Philip & Partners, 7 Vognmagergade, P.O. Box 2227, DK-1018 > Copenhagen K, Denmark. > > > > -- -- Ole I Hougaard Google Aarhus, Denmark +45 8745 9215 --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
