Author: olehougaard
Date: Tue Sep 30 02:58:22 2008
New Revision: 395
Modified:
branches/bleeding_edge/src/array.js
Log:
Faster sort.
Using insertion sort below a certain threshold to give faster sorting of
arrays (esp. short ones).
Review URL: http://codereview.chromium.org/6006
Modified: branches/bleeding_edge/src/array.js
==============================================================================
--- branches/bleeding_edge/src/array.js (original)
+++ branches/bleeding_edge/src/array.js Tue Sep 30 02:58:22 2008
@@ -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,43 @@
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;
+ // The search interval is a[min..max[
+ 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
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
