Reviewers: Mads Ager, Description: Various minor improvements of sort.
Please review this at http://codereview.chromium.org/6035 Affected files: M src/array.js Index: src/array.js =================================================================== --- src/array.js (revision 402) +++ src/array.js (working copy) @@ -650,14 +650,10 @@ // In-place QuickSort algorithm. // For short (length <= 22) arrays, insertion sort is used for efficiency. + var custom_compare = IS_FUNCTION(comparefn); + function Compare(x,y) { - if (IS_UNDEFINED(x)) { - if (IS_UNDEFINED(y)) return 0; - return 1; - } - if (IS_UNDEFINED(y)) return -1; - - if (IS_FUNCTION(comparefn)) { + if (custom_compare) { return comparefn.call(null, x, y); } if (%_IsSmi(x) && %_IsSmi(y)) { @@ -691,15 +687,13 @@ } } // place element at position min==max. - for (var j = min; j < i; j++) { - var tmp = a[j]; - a[j] = element; - element = tmp; + for (var j = i; j > min; j--) { + a[j] = a[j - 1]; } - a[i] = element; + a[min] = element; } } - + function QuickSort(a, from, to) { // Insertion sort is faster for short arrays. if (to - from <= 22) { @@ -743,6 +737,18 @@ %RemoveArrayHoles(this); var length = ToUint32(this.length); + + // Move undefined elements to the end of the array. + for (var i = 0; i < length; ) { + if (IS_UNDEFINED(this[i])) { + length--; + this[i] = this[length]; + this[length] = undefined; + } else { + i++; + } + } + QuickSort(this, 0, length); // We only changed the length of the this object (in --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
