Source code
Revision control
Copy as Markdown
Other Tools
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
// We use varying sorts across the self-hosted codebase. All sorts are
// consolidated here to avoid confusion and re-implementation of existing
// algorithms.
// For sorting small typed arrays.
function InsertionSort(array, from, to, comparefn) {
var item, swap, i, j;
for (i = from + 1; i <= to; i++) {
item = array[i];
for (j = i - 1; j >= from; j--) {
swap = array[j];
if (callContentFunction(comparefn, undefined, swap, item) <= 0) {
break;
}
array[j + 1] = swap;
}
array[j + 1] = item;
}
}
// A helper function for MergeSortTypedArray.
//
// Merge comparefn-sorted slices list[start..<=mid] and list[mid+1..<=end],
// storing the merged sequence in out[start..<=end].
function MergeTypedArray(list, out, start, mid, end, comparefn) {
// Skip lopsided runs to avoid doing useless work.
// Skip calling the comparator if the sub-list is already sorted.
if (
mid >= end ||
callContentFunction(comparefn, undefined, list[mid], list[mid + 1]) <= 0
) {
for (var i = start; i <= end; i++) {
out[i] = list[i];
}
return;
}
var i = start;
var j = mid + 1;
var k = start;
while (i <= mid && j <= end) {
var lvalue = list[i];
var rvalue = list[j];
if (callContentFunction(comparefn, undefined, lvalue, rvalue) <= 0) {
out[k++] = lvalue;
i++;
} else {
out[k++] = rvalue;
j++;
}
}
// Empty out any remaining elements.
while (i <= mid) {
out[k++] = list[i++];
}
while (j <= end) {
out[k++] = list[j++];
}
}
// Iterative, bottom up, mergesort. Optimized version for TypedArrays.
function MergeSortTypedArray(array, len, comparefn) {
assert(
IsPossiblyWrappedTypedArray(array),
"MergeSortTypedArray works only with typed arrays."
);
// Use the same TypedArray kind for the buffer.
var C = ConstructorForTypedArray(array);
var lBuffer = new C(len);
// Copy all elements into a temporary buffer, so that any modifications
// when calling |comparefn| are ignored.
for (var i = 0; i < len; i++) {
lBuffer[i] = array[i];
}
// Insertion sort for small arrays, where "small" is defined by performance
// testing.
if (len < 8) {
InsertionSort(lBuffer, 0, len - 1, comparefn);
return lBuffer;
}
// We do all of our allocating up front.
var rBuffer = new C(len);
// Use insertion sort for the initial ranges.
var windowSize = 4;
for (var start = 0; start < len - 1; start += windowSize) {
var end = std_Math_min(start + windowSize - 1, len - 1);
InsertionSort(lBuffer, start, end, comparefn);
}
for (; windowSize < len; windowSize = 2 * windowSize) {
for (var start = 0; start < len; start += 2 * windowSize) {
// The midpoint between the two subarrays.
var mid = start + windowSize - 1;
// To keep from going over the edge.
var end = std_Math_min(start + 2 * windowSize - 1, len - 1);
MergeTypedArray(lBuffer, rBuffer, start, mid, end, comparefn);
}
// Swap both lists.
var swap = lBuffer;
lBuffer = rBuffer;
rBuffer = swap;
}
return lBuffer;
}