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   */
 28  function 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   */
 42  function 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   */
 58  function 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   */
112  exports.quickSort = function (ary, comparator) {
113    doQuickSort(ary, comparator, 0, ary.length - 1);
114  };