Merge Sort

Merge Sort

Merge Sort is a divide and conquer algorithm. It recursively splits the array in half, sorts each half, then merges the two sorted halves into a single sorted array.

How It Works

Divide: Split the array into two halves at the midpoint.

Conquer: Recursively sort each half.

Merge: Combine the two sorted halves. Compare front elements from each half, take the smaller one, repeat until both halves are exhausted.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return result.concat(left.slice(i), right.slice(j));
}

Complexity

Merge sort is stable (preserves relative order of equal elements) and has guaranteed O(n log n) performance. It is used in Python's sorted() and Java's Arrays.sort() for objects.

Your Task

Implement mergeSort(arr) that returns a new sorted array. You will need a helper merge(left, right) function.