Foundation · Module 4 · Lesson 4
Merge Sort
Divide, recursively sort, and merge stable runs.
Lesson 22 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Merge Sort
Split into runs, then merge in sorted order
Input size
6
Active cells
6
Ranges
1
Progress
1/17
Why this step happens
Divide indexes 0…5 around the middle.
Every recursive call is responsible for sorting exactly its own range.
Theory lesson · Step-by-step
Understand Merge Sort
Divide, recursively sort, and merge stable runs.
Worked approach
Trace the reasoning step by step
- 1Split the range around its middle.
- 2Recursively sort the left and right halves.
- 3Compare the front values of both sorted halves.
- 4Copy the smaller value and append any remainder.
Concrete example
Sort [4, 1, 3, 2] by divide and merge.
- 1Split into [4,1] and [3,2].
- 2Sort halves to [1,4] and [2,3].
- 3Merge to [1,2,3,4].
Balanced splitting gives O(n log n) time.
What must remain true (Loop Invariant)
Each recursive call returns a sorted range; merging preserves order while consuming both halves.
Cost Model
Complexity & Trade-offs
When to use it
- Creating order before searching, grouping, deduplicating, or scanning.
- Selecting records using stability, memory, and input-shape constraints.
- Turning pairwise decisions into monotonic scans.
Common mistakes
- Comparing time alone while ignoring stability and auxiliary memory.
- Breaking duplicate order when stability is required.
- Quoting average performance without worst-case behavior.
Practice prompts
- Reproduce the worked Merge Sort example without looking at the trace.
- Change one input condition and explain whether the Merge Sort invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check