merge sort implementation

MergeSort.ts

/**
 * arr    [5,4,3,2,1,7] length: 6 mid: 2
 *       [5,4,3] [2,1,7]
 *     [5] [4,3] [2] [1,7]
 *        [4] [3]     [1] [7]
 */
function mergeSort(arr: number[], startIndex: number, endIndex: number): number[] {
  if (endIndex <= startIndex) return [arr[startIndex]];

  const mid = Math.floor((startIndex + endIndex) / 2);
  const left = mergeSort(arr, startIndex, mid);
  const right = mergeSort(arr, mid + 1, endIndex);
  return merge(left, right);
}

// merge two sorted array
function merge(arrayA: number[], arrayB: number[]): number[] {
  const output: number[] = [];

  let i = 0;
  let j = 0;

  while (i < arrayA.length && j < arrayB.length) {
    if (arrayA[i] <= arrayB[j]) {
      output.push(arrayA[i]);
      i++;
    } else {
      output.push(arrayB[j]);
      j++;
    }
  }

  while (i < arrayA.length) {
    output.push(arrayA[i]);
    i++;
  }

  while (j < arrayB.length) {
    output.push(arrayB[j]);
    j++;
  }

  return output;
}

const a1 = [1, 2, 4, 9];
const a2 = [2, 3, 4, 5];
console.log(merge(a1, a2)); // 1, 2, 2, 3, 4, 4, 5, 9

const a4 = [2, 1, 0, 13, 21, 7, 6, 0, 1];
console.log(mergeSort(a4, 0, a4.length - 1)); // 0, 0, 1, 1, 2, 6, 7, 13, 21