flip-flop-merge-sort.js

## flip-flop-merge-sort.js
const sorted = arr => {
  const length = arr.length;

  let unsorted = new Array(length),
        sorted = new Array(length);

  const destructiveSort = (unsorted, sorted, offset, length) => {
    if (length === 1) {
      sorted[offset] = unsorted[offset];
    }
    else if (length > 1) {
      const halfLength = Math.floor(length / 2);

      destructiveSort(unsorted, sorted, offset, halfLength);
      [sorted, unsorted] = destructiveSort(unsorted, sorted, offset + halfLength, length - halfLength);

      const z1 = offset + halfLength,
            z2 = offset + length;

      let i1 = offset,
          i2 = offset + halfLength,
          i3 = offset;

      while (i1 < z1 && i2 < z2) {
        if (unsorted[i1] < unsorted[i2]) {
          sorted[i3++] = unsorted[i1++];
        }
        else sorted[i3++] = unsorted[i2++];
      }
      while (i1 < z1) sorted[i3++] = unsorted[i1++];
      while (i2 < z2) sorted[i3++] = unsorted[i2++];
    }
    return [unsorted, sorted];
  }

  for (let i = 0; i < length; ++i) unsorted[i] = arr[i];
  [unsorted, sorted] = destructiveSort(unsorted, sorted, 0, length)
  return sorted;
};

console.log(sorted([]))
console.log(sorted([1]))
console.log(sorted([1, 2]))
console.log(sorted([2, 1]))
console.log(sorted([5, 4, 3, 2, 1]))

## in-place-merge-sort.js
const sorted = arr => {
  const length = arr.length,
        mutableArray = new Array(length),
        buffer = new Array(length);

  const destructiveSort = (offset, length) => {
    // sorting zero or one elements is the degenerate case.
    if (length > 1) {
      const halfLength = Math.floor(length / 2);

      // sort the first and second haves in place
      destructiveSort(offset, halfLength);
      destructiveSort(offset + halfLength, length - halfLength);

      // now merge the two sorted sublists into the buffer
      const z1 = offset + halfLength,
            z2 = offset + length;

      let i1 = offset,
          i2 = offset + halfLength,
          i3 = offset;

      while (i1 < z1 && i2 < z2) {
        if (mutableArray[i1] < mutableArray[i2]) {
          buffer[i3++] = mutableArray[i1++];
        }
        else buffer[i3++] = mutableArray[i2++];
      }
      while (i1 < z1) buffer[i3++] = mutableArray[i1++];
      while (i2 < z2) buffer[i3++] = mutableArray[i2++];

      // and copy the buffer back to the origial
      for (let i = offset; i < z2; ++i) mutableArray[i] = buffer[i];

    }
  }

  for (let i = 0; i < length; ++i) mutableArray[i] = arr[i];
  destructiveSort(0, length)
  return mutableArray;
};