Merge Sort as D&C - Learning Module

Loading content...

0/276

Conquer — Sort Each Half

The Recursive Leap of Faith

"Assume the recursive call works correctly."

This instruction is the heart of the conquer phase, and it's also one of the most challenging concepts for programmers learning divide-and-conquer. How can we assume something works when we're still in the process of defining it?

The answer lies in mathematical induction and structural recursion—powerful reasoning tools that let us trust recursive calls without tracing through every level. In this page, we'll demystify the conquer phase, understand how recursion unfolds, and develop the intuition to confidently write and reason about recursive algorithms.

What You Will Master

By the end of this page, you will understand the conquer phase both mechanically (how the call stack works) and abstractly (why recursive correctness is guaranteed). You'll develop the "recursive faith" that experienced programmers use to write D&C algorithms with confidence.

What Does "Conquer" Mean in Merge Sort?

In the divide-and-conquer paradigm, conquer refers to solving the subproblems created by the divide step. For merge sort:

The Conquer Phase:

mergeSort(A, left, mid)      // Conquer left half
mergeSort(A, mid + 1, right) // Conquer right half

That's it—two recursive calls. But these simple lines hide remarkable complexity:

Each call triggers a complete divide-conquer-combine cycle on its subarray
The calls create a tree of subproblems, solved from leaves to root
All the "real work" (comparisons, movement) happens in base cases and merge operations

The conquer phase is where recursion does the heavy lifting, transforming our divide-and-conquer strategy into actual sorting work.

Two Distinct Cases

The conquer phase handles two cases: 1) Non-trivial subproblems: Make recursive calls. 2) Trivial subproblems (base cases): Return immediately—a single element is already sorted. The algorithm automatically handles both through the base case check.

Independence of Subproblems

A crucial property: the two recursive calls are completely independent. Sorting A[left..mid] doesn't affect or depend on sorting A[mid+1..right]. This independence has profound implications:

Correctness: We can reason about each half separately
Parallelism: The two calls could run on separate processors
Modularity: The algorithm's structure is clean and maintainable

This independence is not automatic in all D&C algorithms. In merge sort, it arises because elements in one half never need to be compared with elements in the other half during the conquer phase—that comparison happens later, in the merge.

The Recursive Leap of Faith

New programmers often struggle with recursion because they try to trace every call mentally. For a call on 8 elements, this means imagining:

4 calls at depth 1
8 calls at depth 2
8 base cases at depth 3
7 merge operations on the way up

That's 27 recursive events to track! For larger arrays, this becomes impossible.

The Leap of Faith

Experienced programmers use a different approach: assume the recursive call works, and verify that if it works, the overall algorithm works.

Here's how this works for merge sort:

Assumption: After mergeSort(A, left, mid) returns, A[left..mid] is sorted.
Assumption: After mergeSort(A, mid+1, right) returns, A[mid+1..right] is sorted.
Verification: Given two sorted halves, does merge produce a sorted whole? Yes.
Conclusion: Therefore, mergeSort(A, left, right) returns a sorted array.

This reasoning is valid because it mirrors mathematical induction: we verify the base case (trivial), then verify the inductive step (if smaller cases work, the larger case works).

Trust the Recursion

When writing recursive code, don't try to trace the full execution. Instead: (1) Handle the base case correctly. (2) Assume recursive calls on smaller inputs work. (3) Show that your code correctly combines results. If all three hold, your recursion is correct by induction.

Why This Works: The Inductive Structure

Reason about merge sort inductively on array size:

Base Case (n ≤ 1): An empty or single-element array is sorted. ✓

Inductive Step (n > 1): Assume merge sort correctly sorts all arrays of size < n.

Left half has size ≤ n/2 < n, so it's correctly sorted (by assumption)
Right half has size ≤ n/2 < n, so it's correctly sorted (by assumption)
Merge combines two sorted arrays into one sorted array (proven separately)
Therefore, the n-element array is correctly sorted. ✓

Conclusion: By strong induction, merge sort correctly sorts arrays of all sizes.

This proof doesn't require tracing any calls—it's purely structural. The algorithm's correctness follows from its structure.

Execution Trace: How Recursion Unfolds

While we use the leap of faith for reasoning, understanding the mechanical execution helps build intuition. Let's trace merge sort on [38, 27, 43, 3]:

Call Tree Execution Order:

mergeSort([38, 27, 43, 3], 0, 3)
├── mergeSort([38, 27], 0, 1)
│   ├── mergeSort([38], 0, 0) → base case, return
│   ├── mergeSort([27], 1, 1) → base case, return
│   └── merge([38], [27]) → [27, 38]
├── mergeSort([43, 3], 2, 3)
│   ├── mergeSort([43], 2, 2) → base case, return
│   ├── mergeSort([3], 3, 3) → base case, return
│   └── merge([43], [3]) → [3, 43]
└── merge([27, 38], [3, 43]) → [3, 27, 38, 43]

Notice the pattern:

Dive left first: All left-half calls complete before right-half calls
Base cases at the bottom: Recursion stops when we reach single elements
Merge on the way up: After both children return, we merge
Leaves to root: Work flows from smallest subproblems to largest

Execution Timeline for [38, 27, 43, 3]
Step	Action	Array State	Stack Depth
1	mergeSort(0,3) called	[38, 27, 43, 3]	1
2	mergeSort(0,1) called	[38, 27, 43, 3]	2
3	mergeSort(0,0) called	[38, 27, 43, 3]	3
4	Base case, return	[38, 27, 43, 3]	2
5	mergeSort(1,1) called	[38, 27, 43, 3]	3
6	Base case, return	[38, 27, 43, 3]	2
7	merge(0,0,1) executed	[27, 38, 43, 3]	2
8	mergeSort(0,1) returns	[27, 38, 43, 3]	1
9	mergeSort(2,3) called	[27, 38, 43, 3]	2
10	mergeSort(2,2) called	[27, 38, 43, 3]	3
11	Base case, return	[27, 38, 43, 3]	2
12	mergeSort(3,3) called	[27, 38, 43, 3]	3
13	Base case, return	[27, 38, 43, 3]	2
14	merge(2,2,3) executed	[27, 38, 3, 43]	2
15	mergeSort(2,3) returns	[27, 38, 3, 43]	1
16	merge(0,1,3) executed	[3, 27, 38, 43]	1
17	mergeSort(0,3) returns	[3, 27, 38, 43]	0

Depth-First Traversal

Merge sort's execution follows a depth-first, left-to-right traversal of the recursion tree. We go as deep as possible on the left before processing the right. This is a natural consequence of the recursive call order in the code.

The Call Stack in Detail

Every recursive call adds a stack frame containing local variables, parameters, and a return address. Understanding the call stack helps debug issues and predict memory usage.

Stack Frame Contents:

Each merge sort call needs to store:

left index (parameter)
right index (parameter)
mid (local variable, computed after base case check)
Return address (where to resume after the call returns)

Stack Evolution:

For mergeSort([38, 27, 43, 3], 0, 3), here's the stack at maximum depth:

stack_trace.txt

Stack State

Maximum stack depth reached at step 3:
 
╔═══════════════════════════════════════╗
║ CALL STACK (grows downward)           ║
╠═══════════════════════════════════════╣
║ Frame 3: mergeSort(0, 0)              ║  ← TOP (current execution)
║   left=0, right=0                     ║
║   (base case - about to return)       ║
╠───────────────────────────────────────╣
║ Frame 2: mergeSort(0, 1)              ║
║   left=0, right=1, mid=0              ║
║   (waiting for left child to return)  ║
╠───────────────────────────────────────╣
║ Frame 1: mergeSort(0, 3)              ║
║   left=0, right=3, mid=1              ║
║   (waiting for left child to return)  ║
╠───────────────────────────────────────╣
║ Frame 0: main()                       ║  ← BOTTOM (entry point)
║   (called mergeSort initially)        ║
╚═══════════════════════════════════════╝

Maximum Stack Depth

For an array of n elements, the maximum stack depth is:

max_depth = ⌈log₂(n)⌉ + 1

This is because:

We halve the problem at each recursion level
It takes log₂(n) halvings to reach size 1
Plus 1 for the initial call

For n = 1,000,000, max_depth ≈ 21. This is very manageable—typical call stacks support thousands of frames. Merge sort is not prone to stack overflow (unlike poorly-implemented quicksort).

Tail Recursion Note

Merge sort is NOT tail-recursive because work (the merge) happens AFTER the recursive calls return. This means we can't easily optimize away the stack frames. However, O(log n) depth is efficient enough that this rarely matters in practice.

Sequential vs. Parallel Execution

Standard merge sort is sequential: we fully process the left half before starting the right half. But the conquer phase's subproblem independence opens the door to parallelism.

Sequential Execution:

mergeSort(A, left, mid)      // Complete this entirely
mergeSort(A, mid + 1, right) // Then start this

Parallel Execution:

parallel {
    thread1: mergeSort(A, left, mid)
    thread2: mergeSort(A, mid + 1, right)
}
wait for both threads
merge(A, left, mid, right)   // Must wait for both to finish

This parallelization is natural and correct because:

The two halves don't overlap in memory
Neither half reads from the other during sorting
The merge only happens after both are complete

Parallelization Benefits

•Theoretical 2x speedup at each level
•Naturally maps to fork-join parallelism
•No synchronization needed during sorting
•Scales with available cores

Parallelization Challenges

•Thread creation overhead
•Cache coherence issues
•Merge phase is harder to parallelize
•Diminishing returns for small subarrays

Practical Parallel Merge Sort:

Real parallel implementations use a hybrid approach:

function parallelMergeSort(A, left, right):
    if right - left < THRESHOLD:
        sequentialMergeSort(A, left, right)  // Avoid thread overhead for small arrays
        return
    
    mid = left + (right - left) / 2
    
    parallel {
        parallelMergeSort(A, left, mid)
        parallelMergeSort(A, mid + 1, right)
    }
    
    merge(A, left, mid, right)  // Can also be parallelized, but more complex

Typical THRESHOLD values are 10,000-100,000 elements. Below this, the overhead of thread management exceeds the benefit of parallelism.

Span and Work

In parallel algorithm analysis, work is total operations (O(n log n) for merge sort), and span is the longest chain of dependencies (O(n) for the final merge). The theoretical speedup is work/span = O(log n), meaning merge sort can benefit from up to log n processors.

Invariants During the Conquer Phase

Invariants are conditions that remain true throughout an algorithm's execution. For the conquer phase, key invariants help us reason about correctness:

Invariant 1: Subarray Boundaries

For every active call mergeSort(A, left, right), we have 0 ≤ left ≤ right < n.

This ensures we never access out-of-bounds indices. It's maintained because:

Initial call uses valid full-array bounds
Midpoint calculation keeps bounds within range
Recursive calls use subranges of valid ranges

Invariant 2: Post-Call Sortedness

When mergeSort(A, left, right) returns, A[left..right] is sorted.

This is the key correctness invariant. It's maintained because:

Base case: single elements are sorted
Inductive case: merge combines two sorted halves into a sorted whole

What Can Go Wrong

If we violate the boundary invariant (e.g., computing mid incorrectly), we get crashes or incorrect results. If we violate the post-call invariant (e.g., buggy merge), sorting fails. Always verify both invariants when debugging merge sort implementations.

Invariant 3: Element Preservation

The multiset of elements in A[left..right] is unchanged by mergeSort.

Merge sort rearranges elements but never creates, destroys, or duplicates them. This is guaranteed because:

Divide: no elements moved
Conquer: recursion on non-overlapping subarrays
Merge: each element from both halves appears exactly once in the output

Invariant 4: In-Place Updates (for index-based implementation)

Only elements in A[left..right] are modified during mergeSort(A, left, right).

This ensures that sorting one subarray doesn't corrupt another. It's guaranteed by:

Array accesses only use indices in [left, right]
Merge uses an auxiliary array, then copies back to [left, right]

Common Pitfalls in the Conquer Phase

The conquer phase looks simple—just two recursive calls—but several subtle bugs can occur:

Common Bugs and Fixes

•Forgetting the base case: Without if left >= right: return, recursion never stops → stack overflow.
•Overlapping subproblems: Using (left, mid) and (mid, right) instead of (left, mid) and (mid+1, right) causes double-processing of the middle element.
•Wrong order of operations: Merging before recursive calls return means merging unsorted arrays → wrong output.
•Inconsistent indexing: Mixing 0-indexed and 1-indexed thinking leads to off-by-one errors throughout.
•Modifying indices: Accidentally changing left or right during the call corrupts subsequent operations.

conquer_bugs.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# BUG 1: Missing base case (stack overflow)
def bad_merge_sort_1(arr, left, right):
    mid = left + (right - left) // 2
    bad_merge_sort_1(arr, left, mid)      # Infinite recursion!
    bad_merge_sort_1(arr, mid + 1, right)
    merge(arr, left, mid, right)
 
# BUG 2: Overlapping subproblems (incorrect result)
def bad_merge_sort_2(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2
    bad_merge_sort_2(arr, left, mid)
    bad_merge_sort_2(arr, mid, right)  # Should be mid + 1!
    merge(arr, left, mid, right)
 
# BUG 3: Merge before conquer (sorting garbage)
def bad_merge_sort_3(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2
    merge(arr, left, mid, right)  # Called too early!
    bad_merge_sort_3(arr, left, mid)
    bad_merge_sort_3(arr, mid + 1, right)
 
# CORRECT implementation
def merge_sort(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)
    merge(arr, left, mid, right)

Debugging Recursive Algorithms

When debugging recursion: (1) Verify the base case terminates correctly. (2) Verify subproblems are strictly smaller. (3) Verify subproblems don't overlap. (4) Verify the order of operations is correct. Test with tiny inputs (size 2, 3, 4) to catch issues early.

Implementation Variations

The conquer phase can be implemented in several equivalent ways, each with trade-offs:

conquer_variations.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Variation 1: Index-based (in-place with auxiliary array)
function mergeSortIndex(arr: number[], left: number, right: number): void {
    if (left >= right) return;
    
    const mid = left + Math.floor((right - left) / 2);
    mergeSortIndex(arr, left, mid);
    mergeSortIndex(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
 
// Variation 2: Slice-based (functional style, new arrays)
function mergeSortSlice(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSortSlice(arr.slice(0, mid));
    const right = mergeSortSlice(arr.slice(mid));
    return mergeArrays(left, right);
}
 
// Variation 3: Iterator-based (lazy evaluation)
function* mergeSortGenerator(arr: number[]): Generator<number[]> {
    if (arr.length <= 1) {
        yield arr;
        return;
    }
    const mid = Math.floor(arr.length / 2);
    yield* mergeSortGenerator(arr.slice(0, mid));
    yield* mergeSortGenerator(arr.slice(mid));
    yield mergeArrays(
        [...mergeSortGenerator(arr.slice(0, mid))].flat(),
        [...mergeSortGenerator(arr.slice(mid))].flat()
    );
}

Comparison of Conquer Phase Implementations
Variation	Space Complexity	Cache Efficiency	Best Use Case
Index-based	O(n) auxiliary	Good (locality)	Production systems
Slice-based	O(n log n) total	Moderate	Teaching, prototyping
Generator-based	O(n log n) + overhead	Poor	Lazy processing, streaming

Summary and What's Next

We've thoroughly explored the conquer phase—the recursive heart of merge sort. The key insights:

Key Takeaways

•The recursive leap of faith: Assume recursive calls work; verify the combination works.
•Inductive correctness: Base case + correct combination = correct algorithm.
•Subproblem independence: Left and right halves can be processed independently (enabling parallelism).
•Call stack mechanics: O(log n) maximum depth; each frame stores parameters and local variables.
•Invariants guide reasoning: Boundary correctness, post-call sortedness, element preservation.
•Beware common pitfalls: Missing base case, overlapping subproblems, wrong operation order.

What's Next:

With divide and conquer phases understood, we arrive at the combine phase: merging sorted halves. This is where the actual sorting work happens—where comparisons are made and elements are moved into final position. The merge operation is the heart of what makes merge sort, and understanding it deeply is essential for mastering the algorithm.

Page Complete

You now understand the conquer phase—both the mechanical execution and the abstract reasoning. The recursive leap of faith is a powerful tool that applies to all D&C algorithms. Next, we'll examine the merge operation, where the algorithm's sorting power is revealed.

Conquer — Sort Each Half

The Recursive Leap of Faith

"Assume the recursive call works correctly."

What You Will Master

What Does "Conquer" Mean in Merge Sort?

In the divide-and-conquer paradigm, conquer refers to solving the subproblems created by the divide step. For merge sort:

The Conquer Phase:

mergeSort(A, left, mid)      // Conquer left half
mergeSort(A, mid + 1, right) // Conquer right half

That's it—two recursive calls. But these simple lines hide remarkable complexity:

Each call triggers a complete divide-conquer-combine cycle on its subarray
The calls create a tree of subproblems, solved from leaves to root
All the "real work" (comparisons, movement) happens in base cases and merge operations

The conquer phase is where recursion does the heavy lifting, transforming our divide-and-conquer strategy into actual sorting work.

Two Distinct Cases

Independence of Subproblems

A crucial property: the two recursive calls are completely independent. Sorting A[left..mid] doesn't affect or depend on sorting A[mid+1..right]. This independence has profound implications:

Correctness: We can reason about each half separately
Parallelism: The two calls could run on separate processors
Modularity: The algorithm's structure is clean and maintainable

The Recursive Leap of Faith

New programmers often struggle with recursion because they try to trace every call mentally. For a call on 8 elements, this means imagining:

4 calls at depth 1
8 calls at depth 2
8 base cases at depth 3
7 merge operations on the way up

That's 27 recursive events to track! For larger arrays, this becomes impossible.

The Leap of Faith

Experienced programmers use a different approach: assume the recursive call works, and verify that if it works, the overall algorithm works.

Here's how this works for merge sort:

Assumption: After mergeSort(A, left, mid) returns, A[left..mid] is sorted.
Assumption: After mergeSort(A, mid+1, right) returns, A[mid+1..right] is sorted.
Verification: Given two sorted halves, does merge produce a sorted whole? Yes.
Conclusion: Therefore, mergeSort(A, left, right) returns a sorted array.

This reasoning is valid because it mirrors mathematical induction: we verify the base case (trivial), then verify the inductive step (if smaller cases work, the larger case works).

Trust the Recursion

Why This Works: The Inductive Structure

Reason about merge sort inductively on array size:

Base Case (n ≤ 1): An empty or single-element array is sorted. ✓

Inductive Step (n > 1): Assume merge sort correctly sorts all arrays of size < n.

Left half has size ≤ n/2 < n, so it's correctly sorted (by assumption)
Right half has size ≤ n/2 < n, so it's correctly sorted (by assumption)
Merge combines two sorted arrays into one sorted array (proven separately)
Therefore, the n-element array is correctly sorted. ✓

Conclusion: By strong induction, merge sort correctly sorts arrays of all sizes.

This proof doesn't require tracing any calls—it's purely structural. The algorithm's correctness follows from its structure.

Execution Trace: How Recursion Unfolds

While we use the leap of faith for reasoning, understanding the mechanical execution helps build intuition. Let's trace merge sort on [38, 27, 43, 3]:

Call Tree Execution Order:

mergeSort([38, 27, 43, 3], 0, 3)
├── mergeSort([38, 27], 0, 1)
│   ├── mergeSort([38], 0, 0) → base case, return
│   ├── mergeSort([27], 1, 1) → base case, return
│   └── merge([38], [27]) → [27, 38]
├── mergeSort([43, 3], 2, 3)
│   ├── mergeSort([43], 2, 2) → base case, return
│   ├── mergeSort([3], 3, 3) → base case, return
│   └── merge([43], [3]) → [3, 43]
└── merge([27, 38], [3, 43]) → [3, 27, 38, 43]

Notice the pattern:

Dive left first: All left-half calls complete before right-half calls
Base cases at the bottom: Recursion stops when we reach single elements
Merge on the way up: After both children return, we merge
Leaves to root: Work flows from smallest subproblems to largest

Execution Timeline for [38, 27, 43, 3]
Step	Action	Array State	Stack Depth
1	mergeSort(0,3) called	[38, 27, 43, 3]	1
2	mergeSort(0,1) called	[38, 27, 43, 3]	2
3	mergeSort(0,0) called	[38, 27, 43, 3]	3
4	Base case, return	[38, 27, 43, 3]	2
5	mergeSort(1,1) called	[38, 27, 43, 3]	3
6	Base case, return	[38, 27, 43, 3]	2
7	merge(0,0,1) executed	[27, 38, 43, 3]	2
8	mergeSort(0,1) returns	[27, 38, 43, 3]	1
9	mergeSort(2,3) called	[27, 38, 43, 3]	2
10	mergeSort(2,2) called	[27, 38, 43, 3]	3
11	Base case, return	[27, 38, 43, 3]	2
12	mergeSort(3,3) called	[27, 38, 43, 3]	3
13	Base case, return	[27, 38, 43, 3]	2
14	merge(2,2,3) executed	[27, 38, 3, 43]	2
15	mergeSort(2,3) returns	[27, 38, 3, 43]	1
16	merge(0,1,3) executed	[3, 27, 38, 43]	1
17	mergeSort(0,3) returns	[3, 27, 38, 43]	0

Depth-First Traversal

The Call Stack in Detail

Every recursive call adds a stack frame containing local variables, parameters, and a return address. Understanding the call stack helps debug issues and predict memory usage.

Stack Frame Contents:

Each merge sort call needs to store:

left index (parameter)
right index (parameter)
mid (local variable, computed after base case check)
Return address (where to resume after the call returns)

Stack Evolution:

For mergeSort([38, 27, 43, 3], 0, 3), here's the stack at maximum depth:

stack_trace.txt

Stack State

Maximum stack depth reached at step 3:
 
╔═══════════════════════════════════════╗
║ CALL STACK (grows downward)           ║
╠═══════════════════════════════════════╣
║ Frame 3: mergeSort(0, 0)              ║  ← TOP (current execution)
║   left=0, right=0                     ║
║   (base case - about to return)       ║
╠───────────────────────────────────────╣
║ Frame 2: mergeSort(0, 1)              ║
║   left=0, right=1, mid=0              ║
║   (waiting for left child to return)  ║
╠───────────────────────────────────────╣
║ Frame 1: mergeSort(0, 3)              ║
║   left=0, right=3, mid=1              ║
║   (waiting for left child to return)  ║
╠───────────────────────────────────────╣
║ Frame 0: main()                       ║  ← BOTTOM (entry point)
║   (called mergeSort initially)        ║
╚═══════════════════════════════════════╝

Maximum Stack Depth

For an array of n elements, the maximum stack depth is:

max_depth = ⌈log₂(n)⌉ + 1

This is because:

We halve the problem at each recursion level
It takes log₂(n) halvings to reach size 1
Plus 1 for the initial call

For n = 1,000,000, max_depth ≈ 21. This is very manageable—typical call stacks support thousands of frames. Merge sort is not prone to stack overflow (unlike poorly-implemented quicksort).

Tail Recursion Note

Sequential vs. Parallel Execution

Standard merge sort is sequential: we fully process the left half before starting the right half. But the conquer phase's subproblem independence opens the door to parallelism.

Sequential Execution:

mergeSort(A, left, mid)      // Complete this entirely
mergeSort(A, mid + 1, right) // Then start this

Parallel Execution:

parallel {
    thread1: mergeSort(A, left, mid)
    thread2: mergeSort(A, mid + 1, right)
}
wait for both threads
merge(A, left, mid, right)   // Must wait for both to finish

This parallelization is natural and correct because:

The two halves don't overlap in memory
Neither half reads from the other during sorting
The merge only happens after both are complete

Parallelization Benefits

•Theoretical 2x speedup at each level
•Naturally maps to fork-join parallelism
•No synchronization needed during sorting
•Scales with available cores

Parallelization Challenges

•Thread creation overhead
•Cache coherence issues
•Merge phase is harder to parallelize
•Diminishing returns for small subarrays

Practical Parallel Merge Sort:

Real parallel implementations use a hybrid approach:

function parallelMergeSort(A, left, right):
    if right - left < THRESHOLD:
        sequentialMergeSort(A, left, right)  // Avoid thread overhead for small arrays
        return
    
    mid = left + (right - left) / 2
    
    parallel {
        parallelMergeSort(A, left, mid)
        parallelMergeSort(A, mid + 1, right)
    }
    
    merge(A, left, mid, right)  // Can also be parallelized, but more complex

Typical THRESHOLD values are 10,000-100,000 elements. Below this, the overhead of thread management exceeds the benefit of parallelism.

Span and Work

Invariants During the Conquer Phase

Invariants are conditions that remain true throughout an algorithm's execution. For the conquer phase, key invariants help us reason about correctness:

Invariant 1: Subarray Boundaries

For every active call mergeSort(A, left, right), we have 0 ≤ left ≤ right < n.

This ensures we never access out-of-bounds indices. It's maintained because:

Initial call uses valid full-array bounds
Midpoint calculation keeps bounds within range
Recursive calls use subranges of valid ranges

Invariant 2: Post-Call Sortedness

When mergeSort(A, left, right) returns, A[left..right] is sorted.

This is the key correctness invariant. It's maintained because:

Base case: single elements are sorted
Inductive case: merge combines two sorted halves into a sorted whole

What Can Go Wrong

Invariant 3: Element Preservation

The multiset of elements in A[left..right] is unchanged by mergeSort.

Merge sort rearranges elements but never creates, destroys, or duplicates them. This is guaranteed because:

Divide: no elements moved
Conquer: recursion on non-overlapping subarrays
Merge: each element from both halves appears exactly once in the output

Invariant 4: In-Place Updates (for index-based implementation)

Only elements in A[left..right] are modified during mergeSort(A, left, right).

This ensures that sorting one subarray doesn't corrupt another. It's guaranteed by:

Array accesses only use indices in [left, right]
Merge uses an auxiliary array, then copies back to [left, right]

Common Pitfalls in the Conquer Phase

The conquer phase looks simple—just two recursive calls—but several subtle bugs can occur:

Common Bugs and Fixes

•Forgetting the base case: Without if left >= right: return, recursion never stops → stack overflow.
•Overlapping subproblems: Using (left, mid) and (mid, right) instead of (left, mid) and (mid+1, right) causes double-processing of the middle element.
•Wrong order of operations: Merging before recursive calls return means merging unsorted arrays → wrong output.
•Inconsistent indexing: Mixing 0-indexed and 1-indexed thinking leads to off-by-one errors throughout.
•Modifying indices: Accidentally changing left or right during the call corrupts subsequent operations.

conquer_bugs.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# BUG 1: Missing base case (stack overflow)
def bad_merge_sort_1(arr, left, right):
    mid = left + (right - left) // 2
    bad_merge_sort_1(arr, left, mid)      # Infinite recursion!
    bad_merge_sort_1(arr, mid + 1, right)
    merge(arr, left, mid, right)
 
# BUG 2: Overlapping subproblems (incorrect result)
def bad_merge_sort_2(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2
    bad_merge_sort_2(arr, left, mid)
    bad_merge_sort_2(arr, mid, right)  # Should be mid + 1!
    merge(arr, left, mid, right)
 
# BUG 3: Merge before conquer (sorting garbage)
def bad_merge_sort_3(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2
    merge(arr, left, mid, right)  # Called too early!
    bad_merge_sort_3(arr, left, mid)
    bad_merge_sort_3(arr, mid + 1, right)
 
# CORRECT implementation
def merge_sort(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) // 2
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)
    merge(arr, left, mid, right)

Debugging Recursive Algorithms

Implementation Variations

The conquer phase can be implemented in several equivalent ways, each with trade-offs:

conquer_variations.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// Variation 1: Index-based (in-place with auxiliary array)
function mergeSortIndex(arr: number[], left: number, right: number): void {
    if (left >= right) return;
    
    const mid = left + Math.floor((right - left) / 2);
    mergeSortIndex(arr, left, mid);
    mergeSortIndex(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
 
// Variation 2: Slice-based (functional style, new arrays)
function mergeSortSlice(arr: number[]): number[] {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSortSlice(arr.slice(0, mid));
    const right = mergeSortSlice(arr.slice(mid));
    return mergeArrays(left, right);
}
 
// Variation 3: Iterator-based (lazy evaluation)
function* mergeSortGenerator(arr: number[]): Generator<number[]> {
    if (arr.length <= 1) {
        yield arr;
        return;
    }
    const mid = Math.floor(arr.length / 2);
    yield* mergeSortGenerator(arr.slice(0, mid));
    yield* mergeSortGenerator(arr.slice(mid));
    yield mergeArrays(
        [...mergeSortGenerator(arr.slice(0, mid))].flat(),
        [...mergeSortGenerator(arr.slice(mid))].flat()
    );
}

Comparison of Conquer Phase Implementations
Variation	Space Complexity	Cache Efficiency	Best Use Case
Index-based	O(n) auxiliary	Good (locality)	Production systems
Slice-based	O(n log n) total	Moderate	Teaching, prototyping
Generator-based	O(n log n) + overhead	Poor	Lazy processing, streaming

Summary and What's Next

We've thoroughly explored the conquer phase—the recursive heart of merge sort. The key insights:

Key Takeaways

•The recursive leap of faith: Assume recursive calls work; verify the combination works.
•Inductive correctness: Base case + correct combination = correct algorithm.
•Subproblem independence: Left and right halves can be processed independently (enabling parallelism).
•Call stack mechanics: O(log n) maximum depth; each frame stores parameters and local variables.
•Invariants guide reasoning: Boundary correctness, post-call sortedness, element preservation.
•Beware common pitfalls: Missing base case, overlapping subproblems, wrong operation order.

What's Next:

Page Complete