Divide as usual.
Merge by making room.
Merge sort sorts two smaller halves, then combines them. Here, that combining happens inside the original array.
A conventional array-based merge uses a temporary buffer. This version keeps the array where it is: when the next right-half value is smaller, save it in value, shift the intervening elements right, and insert it at i.
Split until there is nothing to sort.
mergeSort(left, right) divides at mid. A range with zero or one element returns immediately.
Let both recursive calls finish.
The left call finishes first, then the right call. Only then are both halves ready for their parent merge.
Compare, shift, insert.
If a[i] ≤ a[j], advance i. Otherwise, save a[j], shift a[i…j−1] right, and insert the saved value.
What “in place” means here: the merge uses constant extra workspace and no second array. The recursive sort still uses O(log n) call-stack space. More advanced in-place merge algorithms make different trade-offs; this lesson traces the accessible shift-based version.
One merge, close up.
Start with two sorted halves: [1, 4, 7 | 2, 3, 6]. Here left = 0, mid = 2, and right = 5. The vertical bar marks the changing boundary.
| Decision | Array after the decision | What changed |
|---|---|---|
| 1 ≤ 2: keep 1 | [1, 4, 7 | 2, 3, 6] | i moves from 0 to 1. |
| 4 > 2: insert 2 | [1, 2, 4, 7 | 3, 6] | Save 2. Shift 7, then 4. Insert 2. i = 2, mid = 3, j = 4. |
| 4 > 3: insert 3 | [1, 2, 3, 4, 7 | 6] | Save 3. Shift 7, then 4. Insert 3. i = 3, mid = 4, j = 5. |
| 4 ≤ 6: keep 4 | [1, 2, 3, 4, 7 | 6] | i moves from 3 to 4. |
| 7 > 6: insert 6 | [1, 2, 3, 4, 6, 7 | ] | Shift 7. Insert 6. i = 5, mid = 5, j = 6. |
| j > right: stop | [1, 2, 3, 4, 6, 7] | The right half is empty. The merge is complete. |
Look carefully at a shift. Saving 2 leaves a logical gap at index 3. Copying 7 into that slot creates a temporary duplicate of 7. Then copying 4 right creates a gap at index 1. Writing the saved 2 there restores the complete set of values. The trace shows the actual duplicate values, with a dashed border around the logical gap.
For this example, the merge makes 6 value comparisons (including the initial boundary check), 5 shifts, and 8 array writes (5 shifts + 3 insertions).
The boundary moves with the data.
The split midpoint belongs to the recursive call. Inside mergeInPlace, a local copy of mid becomes the end of the growing left run. Passing it by value lets the merge update its boundary without changing the caller’s midpoint.
| Variable | Meaning during a merge |
|---|---|
left, right | The fixed outer limits of this merge. |
i | The first unprocessed value of the left run. Everything before i in this range is settled. |
mid | The current last index of the left run. |
j | The first unprocessed value of the right run. |
k | The position being filled as the shift travels backward. |
value | The saved right-run value, held safely outside the array. |
After an insertion: ++i, ++mid, ++j.
++i skips the value just placed. ++mid includes the newly inserted element in the left run. ++j moves past the right value that was consumed. At the start of each comparison, j = mid + 1. Between those separate increments, a line-by-line snapshot can briefly show that relation being restored.
k and value are local to the insertion branch. The trace removes k after that branch ends; it is recreated for the next insertion.
Two sorted runs.
One reliable rule.
At the beginning of each outer-loop iteration, the prefix a[left…i−1] is settled, and the unprocessed runs a[i…mid] and a[j…right] are individually sorted. Choose the smaller leading value to extend the prefix.
If the left value is smaller or equal, it is already in the right position. Otherwise, moving the right value to i and shifting the left-run suffix preserves the order inside each run. Each iteration settles one more value, so eventually a run is exhausted. The remaining values are already ordered.
Why equal values keep their order.
The comparison uses ≤. Equal elements from the left half stay ahead of equal elements from the right half. Shifts also preserve the order of the elements being moved. Together, those rules make this implementation stable.
Choose “Equal values” above. Small letters identify the original order: for example, 3ᵃ, 3ᵇ, and 3ᶜ. Their numeric values are equal; the letters never participate in comparisons.
Check your understanding.
During a merge, a[i] and a[j] are equal. What should happen to preserve stability?
Less workspace.
More movement.
A merge of m elements can shift O(m²) values: many right-run values may each cross many left-run values. Across the full sort, this gives O(n²) worst-case time.
| Property | This shift-based version | Typical buffered merge sort |
|---|---|---|
| Worst-case time | O(n²) | O(n log n) |
| Already sorted input | O(n), with the boundary check | Depends on its early-exit optimization |
| Merge workspace | O(1) | O(n) |
| Total auxiliary space | O(log n), from recursion | O(n), including the buffer |
| Stable | Yes, with ≤ | Yes, when ties take the left value |
The boundary check a[mid] ≤ a[mid + 1] returns when the two sorted halves already fit together. An already sorted input still makes O(n) recursive calls, so the whole sort takes O(n) time, not O(1).
The live counters count value-to-value comparisons, assignments to array slots, and shifts. They exclude index comparisons, scalar assignments, and the visualizer’s own storage. The visualizer records snapshots for replay; the C++ sorting algorithm does not.
The complete C++ program.
The source panel above follows these same two functions. This complete program adds the headers, sample array, and output. It works with empty arrays, one element, negative values, and duplicates.
Expand the complete program
To compile: g++ -std=c++17 merge_sort.cpp -o merge_sort
The interactive trace accepts 1–16 integers from −999 to 999 to keep each operation readable. The C++ implementation is not limited to 16 elements.
The mistakes worth catching.
Shifting forward.
Writing from left to right overwrites values before they are copied. Start k at j and work backward.
Forgetting to grow mid.
An insertion adds one element to the left run. Without ++mid, later comparisons can stop before that run is fully processed.
Comparing with < instead of ≤.
The values still sort, but right-half duplicates can jump ahead of left-half duplicates. Stability is lost.
Merging halves that are not sorted.
The merge relies on both runs already being sorted. In the whole sort, recursion guarantees that precondition. In merge-only mode, the lesson checks it.
Calling the entire sort O(1) space.
The merge uses a constant number of variables. Recursive calls still need O(log n) stack space.