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. --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
