Merge Sort

Merge Sort is a divide-and-conquer algorithm that recursively divides the input array into smaller subarrays, sorts them, and then merges the sorted subarrays back together. It is one of the most efficient comparison-based sorting algorithms.

Complexity Analysis

Best Case

O(n log n)

Average Case

O(n log n)

Worst Case

O(n log n)

Space Complexity

O(n)

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    return [...result, ...left, ...right];
}

How Merge Sort Works

Merge Sort follows the divide-and-conquer paradigm. It divides the unsorted array into two halves, recursively sorts each half, and then merges the sorted halves to produce the final sorted array.

Algorithm Steps:

  1. Divide: Split the array into two roughly equal halves
  2. Conquer: Recursively sort each half by repeating the divide step
  3. Base Case: When a subarray has only one element, it is already sorted
  4. Merge: Combine two sorted subarrays into a single sorted array
  5. Repeat: Continue until the entire array is sorted

The Merge Process:

  1. Create two pointers, one for each sorted subarray
  2. Compare elements at both pointers
  3. Add the smaller element to the result array
  4. Move the pointer of the chosen element forward
  5. Repeat until one subarray is exhausted
  6. Append remaining elements from the other subarray

Key Characteristics:

  • Stable: Maintains relative order of equal elements
  • Predictable: Always O(n log n) time complexity
  • Recursive: Uses system call stack for recursion
  • Not in-place: Requires additional space O(n)
  • Parallel-friendly: Easy to parallelize the recursive calls

Advantages:

  • Guaranteed performance: Always O(n log n) regardless of input
  • Stable sorting: Preserves order of equal elements
  • Works well with linked lists: Natural fit for linked list sorting
  • Predictable memory usage: Space requirement is always O(n)

Disadvantages:

  • Space complexity: Requires additional O(n) space
  • Constant overhead: Slower than quicksort for small arrays
  • Recursion depth: Stack overflow risk for very large arrays