Merge Sort

Tags

Merge Sort

Category

Sorting

Difficulty

Medium

Problem Statement

Implement Merge Sort, a divide-and-conquer sorting algorithm that recursively splits an array into halves, sorts each half, and merges the sorted halves back together.

Intuition

A single element is trivially sorted. By recursively halving the array until we reach single elements and then merging sorted halves back together, we build up a fully sorted array. The merge step is the core operation: combining two sorted sequences into one sorted sequence can be done in linear time.

Approach

  1. If the array has 0 or 1 elements, it is already sorted. Return.
  2. Find the midpoint and recursively sort the left half and the right half.
  3. Merge the two sorted halves:
    • Use two pointers, one for each half.
    • Compare elements at both pointers; append the smaller one to the result.
    • When one half is exhausted, append the remaining elements of the other.
  4. Copy the merged result back into the original array (or return it).

Pseudocode

function mergeSort(array):
    if length(array) <= 1:
        return array

    mid = length(array) / 2
    left = mergeSort(array[0..mid])
    right = mergeSort(array[mid..end])

    return merge(left, right)

function merge(left, right):
    result = []
    i = 0
    j = 0

    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while i < length(left):
        result.append(left[i])
        i += 1

    while j < length(right):
        result.append(right[j])
        j += 1

    return result

Time & Space Complexity

  • Time: O(n log n) — the array is halved log n times, and each level of recursion performs O(n) work during the merge step.
  • Space: O(n) — auxiliary space is needed for the merge step. The recursion stack adds O(log n) but is dominated by the O(n) merge buffer. An in-place variant exists but is significantly more complex.

Key Insights

  • Merge Sort is stable: equal elements retain their relative order because the merge step uses <= (taking from the left array first on ties).
  • Unlike Quick Sort, Merge Sort guarantees O(n log n) worst-case performance with no degenerate inputs.
  • The merge operation is the only step that does real work; the divide step is just index arithmetic.
  • Merge Sort is well-suited for linked lists (where merging is O(1) space) and external sorting (large data that does not fit in memory).

Edge Cases

  • Empty array: return empty.
  • Single element: return as-is.
  • Already sorted array: still O(n log n) — Merge Sort does not adapt to pre-sorted input.
  • All elements identical: works correctly, merge just appends them in order.
  • Odd-length array: one half has one more element; handled naturally by the midpoint calculation.

Linked mentions