1/* -*- Mode: js; js-indent-level: 2; -*- */
2/*
3 * Copyright 2011 Mozilla Foundation and contributors
4 * Licensed under the New BSD license. See LICENSE or:
5 * http://opensource.org/licenses/BSD-3-Clause
6 */
7
8// It turns out that some (most?) JavaScript engines don't self-host
9// `Array.prototype.sort`. This makes sense because C++ will likely remain
10// faster than JS when doing raw CPU-intensive sorting. However, when using a
11// custom comparator function, calling back and forth between the VM's C++ and
12// JIT'd JS is rather slow *and* loses JIT type information, resulting in
13// worse generated code for the comparator function than would be optimal. In
14// fact, when sorting with a comparator, these costs outweigh the benefits of
15// sorting in C++. By using our own JS-implemented Quick Sort (below), we get
16// a ~3500ms mean speed-up in `bench/bench.html`.
17
18/**
19 * Swap the elements indexed by `x` and `y` in the array `ary`.
20 *
21 * @param {Array} ary
22 *        The array.
23 * @param {Number} x
24 *        The index of the first item.
25 * @param {Number} y
26 *        The index of the second item.
27 */
28function swap(ary, x, y) {
29  var temp = ary[x];
30  ary[x] = ary[y];
31  ary[y] = temp;
32}
33
34/**
35 * Returns a random integer within the range `low .. high` inclusive.
36 *
37 * @param {Number} low
38 *        The lower bound on the range.
39 * @param {Number} high
40 *        The upper bound on the range.
41 */
42function randomIntInRange(low, high) {
43  return Math.round(low + (Math.random() * (high - low)));
44}
45
46/**
47 * The Quick Sort algorithm.
48 *
49 * @param {Array} ary
50 *        An array to sort.
51 * @param {function} comparator
52 *        Function to use to compare two items.
53 * @param {Number} p
54 *        Start index of the array
55 * @param {Number} r
56 *        End index of the array
57 */
58function doQuickSort(ary, comparator, p, r) {
59  // If our lower bound is less than our upper bound, we (1) partition the
60  // array into two pieces and (2) recurse on each half. If it is not, this is
61  // the empty array and our base case.
62
63  if (p < r) {
64    // (1) Partitioning.
65    //
66    // The partitioning chooses a pivot between `p` and `r` and moves all
67    // elements that are less than or equal to the pivot to the before it, and
68    // all the elements that are greater than it after it. The effect is that
69    // once partition is done, the pivot is in the exact place it will be when
70    // the array is put in sorted order, and it will not need to be moved
71    // again. This runs in O(n) time.
72
73    // Always choose a random pivot so that an input array which is reverse
74    // sorted does not cause O(n^2) running time.
75    var pivotIndex = randomIntInRange(p, r);
76    var i = p - 1;
77
78    swap(ary, pivotIndex, r);
79    var pivot = ary[r];
80
81    // Immediately after `j` is incremented in this loop, the following hold
82    // true:
83    //
84    //   * Every element in `ary[p .. i]` is less than or equal to the pivot.
85    //
86    //   * Every element in `ary[i+1 .. j-1]` is greater than the pivot.
87    for (var j = p; j < r; j++) {
88      if (comparator(ary[j], pivot) <= 0) {
89        i += 1;
90        swap(ary, i, j);
91      }
92    }
93
94    swap(ary, i + 1, j);
95    var q = i + 1;
96
97    // (2) Recurse on each half.
98
99    doQuickSort(ary, comparator, p, q - 1);
100    doQuickSort(ary, comparator, q + 1, r);
101  }
102}
103
104/**
105 * Sort the given array in-place with the given comparator function.
106 *
107 * @param {Array} ary
108 *        An array to sort.
109 * @param {function} comparator
110 *        Function to use to compare two items.
111 */
112exports.quickSort = function (ary, comparator) {
113  doQuickSort(ary, comparator, 0, ary.length - 1);
114};
115