Dustin Boston

/**
 * @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
 */
export 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
 */
export 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");
})();

/*!
 * @file Implements the merge sort 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.
 */

import {merge, mergeSort} from "../../../../data/algorithms/src/merge_sort.ts";
import {assertEquals} from "$assert";

test("mergeSort", () => {
  const A = [5, 2, 4, 7, 1, 3, 2, 6];
  mergeSort(A, 0, A.length - 1);
  assertEquals(A.toString(), "1,2,2,3,4,5,6,7");
});

test("merge", () => {
  const A = [2, 4, 5, 7, 1, 2, 3, 6];
  merge(A, 0, 3, A.length - 1);
  assertEquals(A.toString(), "1,2,2,3,4,5,6,7");
});