Merge Sort

A divide-and-conquer sorting technique that splits the array into halves, recursively sorts each half, and then merges the sorted halves.

/**
 * @file Merge Sort
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/*!
 * @file Implements algorithm in TypeScript.
 * @author Dustin Boston <mail@dustin.boston>
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 * *Introduction to Algorithms*. (2nd ed). The MIT Press.
 */

/**
 * Merge sort
 *
 * Recursively divides the array, sorts each part, then merges the sorted
 * sub-sequences together.
 *
 * - Recursive divide and conquer
 * - Worst-case running time: O(n log n)
 * - Rate of growth: O(n)
 *
 * @param arr - The array to be sorted
 * @param startIndex - Starting index of the array segment
 * @param endIndex - Ending index of the array segment
 */
function mergeSort(
  array: number[],
  startIndex: number,
  endIndex: number,
): void {
  if (startIndex < endIndex) {
    const middleIndex = Math.floor((startIndex + endIndex) / 2);
    mergeSort(array, startIndex, middleIndex);
    mergeSort(array, middleIndex + 1, endIndex);
    merge(array, startIndex, middleIndex, endIndex);
  }
}

/**
 * Merge Function used in Merge Sort
 *
 * - Worst-case running time: O(n)
 * - Rate of growth: O(n)
 *
 * @param arr - The array containing segments to be merged
 * @param startIndex - Starting index of the first segment
 * @param middleIndex - Ending index of the first segment / Starting index of
 *   the second segment - 1
 * @param endIndex - Ending index of the second segment
 */
function merge(
  array: number[],
  startIndex: number,
  middleIndex: number,
  endIndex: number,
): void {
  const leftArraySize = middleIndex - startIndex + 1;
  const rightArraySize = endIndex - middleIndex;

const leftArray: number[] = Array.from({length: leftArraySize});
  const rightArray: number[] = Array.from({length: rightArraySize});

for (let i = 0; i < leftArraySize; i++) {
    leftArray[i] = array[startIndex + i];
  }

for (let index = 0; index < rightArraySize; index++) {
    rightArray[index] = array[middleIndex + index + 1];
  }

leftArray.push(Infinity);
  rightArray.push(Infinity);

let leftIndex = 0;
  let rightIndex = 0;

for (let arrayIndex = startIndex; arrayIndex <= endIndex; arrayIndex++) {
    if (leftArray[leftIndex] <= rightArray[rightIndex]) {
      array[arrayIndex] = leftArray[leftIndex];
      leftIndex++;
    } else {
      array[arrayIndex] = rightArray[rightIndex];
      rightIndex++;
    }
  }
}

// Usage:
(() => {
  const array1 = [5, 2, 4, 7, 1, 3, 2, 6];
  mergeSort(array1, 0, array1.length - 1);

const actual = array1.toString();
  const expected = '1,2,2,3,4,5,6,7';

if (actual !== expected) {
    throw new Error(`Expected ${expected} but got ${actual}`);
  }

console.log('Merge sort passed');
})();