DAA 14_merge_sort Divide & Conquer

Merge Sort — Interactive Visual Tutorial

Merge Sort splits the array until single elements, then merges two sorted halves using pointers. It guarantees O(n log n) time (even worst case) but needs O(n) extra space.

Visualizer
Step: 0 / 0
Smaller ms = faster (e.g., 120 fast, 1000 slow).
Legend Active Range Left half Right half mid pointer write
Ops: 0
Current Range
—
mid
—
Comparisons
0
Writes (temp+copy)
0
Message
Enter an array and click Start.
Recursion Stack (Top = Latest) Depth: 0

Merge is the heart: compare heads of L and R, push smaller into output, then copy back.

Live Pseudocode

Highlighted line matches the current step.

MergeSort(A, l, r):
if l >= r: return
mid = ⌊(l + r)/2⌋
MergeSort(A, l, mid)
MergeSort(A, mid+1, r)
Merge(A, l, mid, r)
Merge(A, l, mid, r):
i = l, j = mid+1, temp = []
while i <= mid and j <= r:
if A[i] <= A[j]: temp.push(A[i]); i++
else: temp.push(A[j]); j++
append remaining left/right to temp
copy temp back to A[l..r]
Tip: MergeSort’s total work is “n work per level” × “log n levels”.
Complexity (Quick Visual)
Choose n (array size)
n = 16
What it means
Depth ≈ 4 levels
Work per level ≈ 16 merges/writes
Total work ≈ 64 → O(n log n)
Extra space ≈ O(n)
Quick Look
Facts
✅ Always O(n log n) (best/avg/worst)
✅ Stable (equal elements keep order)
⚠️ Needs extra memory (temp array)