Merge Sort

Merge Sort is an efficient sorting algorithm that uses a divide-and-conquer approach. It works by breaking an array into smaller pieces, sorting those pieces, and then merging them back together.

Unlike algorithms that are more simple, Merge Sort performs well on large datasets and guarantees consistent performance. However, it requires additional memory to store temporary arrays during the merging process.

How It Works

Merge Sort works by dividing and combining:

Split the array into two halves.
Repeat the process for each half until each subarray contains one element.
Merge the subarrays back together in sorted order.
Continue merging until the entire array is rebuilt.

During the merge step:

Compare the first elements of each subarray.
Take the smaller value and add it to the result.
Move to the next element in that subarray.
Repeat until all elements are merged.

This process ensures that the final array is fully sorted.

JavaScript Example


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;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result
    .concat(left.slice(i))
    .concat(right.slice(j));
}

// Example usage
const values = [38, 27, 43, 3, 9, 82, 10];

console.log(mergeSort(values)); // [3, 9, 10, 27, 38, 43, 82]