Sorting Algorithm

Merge Sort

A divide-and-conquer algorithm: split the array in half recursively until each piece has one element, then merge pairs of sorted pieces back together. Every merge step compares the fronts of two already-sorted runs, which is what guarantees O(n log n) no matter how the input is arranged.

BestO(n log n)
AverageO(n log n)
WorstO(n log n)
SpaceO(n)
StableYes

Try It — Animated Flow

29
8
44
15
3
37
21
Merge sort repeatedly merges sorted runs, doubling their size each pass, until one sorted run remains.
Step 1 / 28
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

External sorting of huge files
When data is too large to fit in memory, merge sort's sequential, chunk-at-a-time access pattern makes it the standard approach for sorting data on disk (e.g. large database sorts).
Sorting linked lists
Merge sort needs no random access — only sequential traversal — so it's the textbook-preferred sort for linked lists, where arrays' O(1) indexing advantage doesn't apply.
Stable multi-key sorts
Sorting a table by 'last name, then first name' requires a stable sort so a prior sort's order is preserved — merge sort guarantees that.
The engine inside Tim Sort
Python's and Java's real-world sort (Tim Sort) is fundamentally merge sort, optimized to merge naturally-occurring runs instead of single elements.

Trade-offs

Reach for it when
  • You need a guaranteed O(n log n), no matter the input
  • Stability is required (equal elements must keep their order)
  • You're sorting a linked list or external (disk-based) data
Avoid it when
  • Memory is tight — it needs O(n) extra space
  • The array is small (insertion sort has less overhead)
  • In-place sorting is a hard requirement