Merge Sort Visualization & Animation

Divides the array in half, sorts each half, then merges — guaranteed O(n log n) and stable.

## What is it? Merge Sort is a classic divide-and-conquer sorting algorithm. It recursively splits the array in half, sorts each half, then merges the two sorted halves back together. ## How it works - **Divide:** split the array into two halves at the midpoint - **Conquer:** recursively sort each half - **Merge:** merge the two sorted halves into a single sorted array by comparing elements front-to-front and placing the smaller one first - Base case: an array of 0 or 1 elements is already sorted ## When to use - When you need a guaranteed O(n log n) sort regardless of input - Sorting linked lists (no random access needed) - External sorting (data too large to fit in RAM) - When stability is required ## Key Points - Stable sort — equal elements maintain relative order - Not in-place — requires O(n) auxiliary space for the merge step - Consistent O(n log n) time in all cases (best, average, worst) - Good for large datasets where predictability matters

Category: algorithms

Difficulty: intermediate

Time Complexity: O(n log n)

Space Complexity: O(n)

Merge Sort

intermediate

Divides the array in half, sorts each half, then merges — guaranteed O(n log n) and stable.

GFGLeetCode
PHASE 1 — SPLITTING into smaller pieces
38
27
43
3
9
82
Left array
Right array
Merged / sorted
We start with [38, 27, 43, 3, 9, 82]. Merge Sort splits the array into halves, sorts each half, then merges them back.