Merge Sort Overview

Stable divide-and-conquer sorting: split in halves until size 1, then perform linear merges level by level. Each element participates in log n merge passes giving deterministic O(n log n) time.

Time

O(n log n)

All inputs

Space

O(n)

Aux buffer

Stability

Stable

Preserves ties

Recurrence

2T(n/2)+n

Master: n log n

Mechanics

Stages

1Divide sequence into two halves recursively
2Reach base single-element segments (already sorted)
3Merge sibling sorted runs via two-pointer scan
4Ascend levels building larger sorted runs until full array

Key Characteristics

•Predictable O(n log n) regardless of input ordering
•Stable: equal keys keep original relative order
•Good for linked lists (can merge in-place with pointers)
•External merge (k-way) scales to large disk datasets

Recurrence

T(n) = 2T(n/2) + n. Master Theorem (a=2, b=2, f(n)=n) gives T(n) = Θ(n log n). Each of the log n levels performs linear merging over n total elements.

Level work: n + n + ... (log n levels) → n log n

Guarantees & Stability

No worst-case degradation (contrast quicksort pivot path)
Stable ordering keeps secondary key precedence intact
Deterministic memory footprint ~ n auxiliary
Parallelizable: independent merges on same level

Practical tweak: switch to insertion sort on tiny subarrays to reduce overhead; bottom-up variant avoids recursion stack.

Bottom-up strategy: Iteratively merge runs of size 1,2,4,... eliminating recursion and enabling easy adaptive detection of presorted runs.

Parallelization: Higher-level splits farm out work to threads; merging can be balanced by splitting large runs at proportional ranks.

View Theory Run Simulation

Quick Sort