inplace merge sort

gistfile1.js

// inplace merge sort
// http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
(function () {
  "use strict";

  var floor = Math.floor;

  function lower(a, from, to, value, compare) {
    while (to > from) {
      var middle = from + floor((to - from) / 2);
      if (compare(a[middle], value) < 0) {
        from = middle + 1;
      } else {
        to = middle;
      }
    }
    return from;
  }

  function upper(a, from, to, value, compare) {
    while (to > from) {
      var middle = from + floor((to - from) / 2);
      if (compare(value, a[middle]) < 0) {
        to = middle;
      } else {
        from = middle + 1;
      }
    }
    return from;
  }

  function reverse(a, from, to) {
    --from;
    while (++from < --to) {
      var tmp = a[from];
      a[from] = a[to];
      a[to] = tmp;
    }
  }

  function rotate(a, from, pivot, to) {
    if (from < pivot && pivot < to) {
      reverse(a, from, pivot);
      reverse(a, pivot, to);
      reverse(a, from, to);
    }
  }

  function merge(a, from, pivot, to, compare) {
    if (from < pivot && pivot < to && compare(a[pivot], a[pivot - 1]) < 0) {
      if (to - from === 2) {
        reverse(a, from, to);
      } else {
        var firstCut = 0;
        var secondCut = 0;
        if (pivot - from > to - pivot) {
          firstCut = from + floor((pivot - from) / 2);
          secondCut = lower(a, pivot, to, a[firstCut], compare);
        } else {
          secondCut = pivot + floor((to - pivot) / 2);
          firstCut = upper(a, from, pivot, a[secondCut], compare);
        }
        rotate(a, firstCut, pivot, secondCut);
        var middle = secondCut - pivot + firstCut;
        merge(a, middle, secondCut, to, compare);
        merge(a, from, firstCut, middle, compare);
      }
    }
  }

  function mergeSort(a, from, to, compare) {
    if (to - from > 1) {
      var middle = from + floor((to - from) / 2);
      mergeSort(a, from, middle, compare);
      mergeSort(a, middle, to, compare);
      merge(a, from, middle, to, compare);
    }
  }

  Object.defineProperty(Array.prototype, "inPlaceMergeSort", {
    writable: true,
    enumerable: false,
    configurable: true,
    value: function (compare) {
      mergeSort(this, 0, this.length, compare);
      return this;
    }
  });

}());