CS Algorithms 101 – Merge Sort

Merge Sort is a sorting algorithm that works by dividing an array into smaller sub-arrays, sorting those sub-arrays, and then merging them back together to produce a sorted result.

The algorithm works by first dividing the array in half repeatedly until the sub-arrays contain only one element each. This is the base case of the recursion.

Once each sub-array contains only one element, the algorithm merges pairs of sub-arrays back together, comparing the first element of each sub-array and adding the smaller element to a new array. This process is repeated until all sub-arrays are merged back together into a single sorted array.

The merge step is repeated recursively until the entire array is sorted. The result is a sorted array with each element in the correct order.

Merge Sort is considered one of the most efficient sorting algorithms and is often used in computer science and programming because of its speed and accuracy.

function mergeSort(arr) {
  // Base case: if the array has one or zero elements, it is already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Split the array into two halves
  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  // Recursively sort the two halves
  const sortedLeft = mergeSort(leftArr);
  const sortedRight = mergeSort(rightArr);

  // Merge the two sorted halves back together
  return merge(sortedLeft, sortedRight);
}

function merge(leftArr, rightArr) {
  const result = [];

  while (leftArr.length && rightArr.length) {
    if (leftArr[0] < rightArr[0]) {
      result.push(leftArr.shift());
    } else {
      result.push(rightArr.shift());
    }
  }

  return result.concat(leftArr, rightArr);
}

// Example usage
const arr = [38, 27, 43, 3, 9, 82, 10];
const sortedArr = mergeSort(arr);

console.log(sortedArr); // Output: [3, 9, 10, 27, 38, 43, 82]

Here are the steps of the Merge Sort algorithm:

1. The mergeSort function takes an array arr and recursively divides it into smaller sub-arrays until each sub-array contains only one element. This is the base case of the recursion.
2. Once the base case is reached, the merge function is called to merge the sorted sub-arrays back together. The merge function takes two sorted arrays leftArr and rightArr as inputs and combines them into a single sorted array.
3. The merge function works by comparing the first elements of leftArr and rightArr, and adding the smaller element to the result array. The index of the array with the smaller element is incremented, and the comparison is repeated until one of the arrays is fully traversed.
4. Once one of the arrays is fully traversed, the remaining elements of the other array are added to the end of the result array.
5. The merge function returns the sorted result array to the mergeSort function.
6. The mergeSort function repeats this process recursively for each pair of sub-arrays until the entire array is sorted.
7. The final sorted array is returned by the mergeSort function.