MV's blog

Merge Sort

Merge sort is one of the two classic sorting algorithms that are used widely in the world's computational infrastructure. The idea of merge sort is to divide an array into two halves recursively, sort each of the halves and then merge the result.

Example:

Time complexity

O(N) = N * log(N)

Sample typescript implementation for sorting numbers in ascending order.

function mergeSort(numbers: number[]) {
  return sort(numbers, [], 0, numbers.length - 1);
}

function sort(
  numbers: number[],
  aux: number[],
  start: number,
  end: number,
): void {
  if (start >= end) return;

  const mid = start + Math.floor((end - start) / 2);
  sort(numbers, aux, start, mid);
  sort(numbers, aux, mid + 1, end);
  merge(numbers, aux, start, mid, end);
}

function merge(
  numbers: number[],
  aux: number[],
  start: number,
  mid: number,
  end: number,
) {
  let i = start;
  let j = mid + 1;

  for (let k = start; k <= end; k++) {
    aux[k] = numbers[k];
  }

  for (let k = start; k <= end; k++) {
    if (aux[i] > aux[j]) {
      numbers[k] = aux[j++];
    } else if (aux[i] < aux[j]) {
      numbers[k] = aux[i++];
    } else if (i > mid) {
      numbers[k] = aux[j++];
    } else {
      numbers[k] = aux[i++];
    }
  }
}

Image taken from: https://www.coursera.org/learn/algorithms-part1/