merge sort

sort.js

// `Array#sort` implementation using the merge sort
// Notes:
// 1) calls comparator for undefined values, holes, values from the prototype chain;
// 2*) replaces holes with undefined values or values from the prototype chain;
// 3*) does not use `ToObject(this)`, `ToLength(this.length)`;
// 4*) does not throw errors for non-undefined non-function `comparefn`.
// 5*) uses `Math`, `Math.floor`, `String`, `Array`.
// 6*) calls setters of `Array.prototype` during internal buffer initialization.
// * This behaviour is inconsistent across browsers even for built-in `Array#sort`.

Array.prototype.sort = function (compare) {
  "use strict";
  var mergeSort = function (array, start, end, comparefn, copy) {
    var middle = start + Math.floor((end - start) / 2);
    if (middle - start > 1) {
      mergeSort(copy, start, middle, comparefn, array);
    }
    if (end - middle > 1) {
      mergeSort(copy, middle, end, comparefn, array);
    }
    var i = start;
    var j = middle;
    var k = start;
    while (i < middle && j < end) {
      if (comparefn(copy[j], copy[i]) < 0) {
        array[k] = copy[j];
        k += 1;
        j += 1;
      } else {
        array[k] = copy[i];
        k += 1;
        i += 1;
      }
    }
    while (j < end) {
      array[k] = copy[j];
      k += 1;
      j += 1;
    }
    while (i < middle) {
      array[k] = copy[i];
      k += 1;
      i += 1;
    }
  };
  var comparefn = compare != undefined ? compare : function (x, y) {
    return String(x) < String(y) ? -1 : +1;
  };
  var length = this.length;
  if (length > 1) {
    var buffer = new Array(length);
    var n = 0;
    while (n < length) {
      buffer[n] = this[n];
      n += 1;
    }
    mergeSort(this, 0, length, comparefn, buffer);
  }
  return this;
};