Merge Sort

Split in half, sort each half, merge the sorted halves. Guaranteed O(n log n), stable, and the merge step is sequential-access friendly — the backbone of external sorting.

Category: Sorting
Time complexity: O(n log n)
Space complexity: O(n)

Pseudocode

mergeSort(lo, hi)
  split at mid
  mergeSort each half
  merge sorted halves
done

Reference implementation

def merge_sort(a):
    if len(a) &lt;= 1: return a
    mid = len(a) // 2
    return merge(
        merge_sort(a[:mid]),
        merge_sort(a[mid:]))

Open the interactive Merge Sort visualisation →