Merge Sort as D&C - Learning Module

Loading content...

0/276

Divide — Split in Half

The Deceptively Simple First Step

"Just split the array in half."

This instruction sounds trivially simple—so simple that many learners skip past it without thought. Yet this single operation—the divide phase of merge sort—contains subtle decisions that determine the algorithm's correctness, efficiency, and behavior. Getting the divide phase wrong can cause infinite recursion, off-by-one errors, or incorrect sorting.

In this page, we'll treat the divide phase with the respect it deserves: examining exactly what it means to split an array, the mathematical precision required, and the implementation pitfalls that await the unwary.

What You Will Master

By the end of this page, you will understand the divide phase at a deep level: why we compute midpoints the way we do, how to handle odd-length arrays, the importance of guaranteeing progress toward base cases, and how this O(1) operation sets up the entire algorithm for success.

What Does "Divide" Mean in This Context?

In the context of divide-and-conquer, divide means decomposing a problem into smaller subproblems. For merge sort specifically, this means:

Given: An array A[left..right] with n = right - left + 1 elements to sort.

Compute: A midpoint mid such that:

A[left..mid] contains approximately n/2 elements
A[mid+1..right] contains approximately n/2 elements
Both subarrays are non-empty (unless the original has ≤1 element)

The division is logical, not physical. We don't create new arrays in the divide phase—we simply determine the boundaries of subproblems. The original array remains intact; we just describe which indices belong to which subproblem.

Logical vs. Physical Division

Some implementations do create new arrays (extracting left and right halves), but this is an implementation choice, not a requirement of the divide phase. The conceptual operation is simply determining where to split. Physical copying, if done, happens as part of the combine phase's auxiliary space.

The Fundamental Invariant

The divide phase must maintain a crucial invariant:

Progress Invariant: Each subproblem must be strictly smaller than the original problem.

If a subproblem is the same size as the original (or larger), we have infinite recursion. This invariant is surprisingly easy to violate with off-by-one errors:

// DANGER: This can cause infinite recursion!
function mergeSort(A, left, right):
    mid = left                           // BAD: left subproblem is [left..left] = 1 element
    mergeSort(A, left, mid)              // OK: size 1
    mergeSort(A, mid, right)             // INFINITE LOOP: same as original if left=mid!

The correct midpoint calculation ensures that both subproblems are strictly smaller for any input with more than one element.

The Midpoint Calculation: A Deep Dive

Computing the midpoint of a range seems trivial: just average the endpoints. But this simple operation has historically caused bugs in production code, including in widely-used libraries.

The Naive Approach (Dangerous)

mid = (left + right) / 2

This works mathematically, but has a critical flaw: integer overflow. If left and right are both large (say, around 2 billion on a 32-bit system), their sum exceeds the maximum integer value, causing overflow and incorrect results.

The Safe Approach

mid = left + (right - left) / 2

This formula computes the same value but avoids overflow. By computing (right - left) first, we ensure the intermediate value never exceeds the range size, which is always ≤ the maximum array size.

A Real-World Bug

In 2006, Joshua Bloch (author of 'Effective Java') discovered that Java's binary search had used the naive formula since 1946! The bug had existed undetected for decades because arrays were rarely large enough to trigger it. The fix was simply changing to the safe formula. This shows that even 'trivial' operations deserve careful thought.

Mathematical Equivalence

Let's prove the formulas are equivalent:

mid = (left + right) / 2
    = (left + right) / 2
    = (left + left - left + right) / 2
    = (2*left + (right - left)) / 2
    = left + (right - left) / 2    ✓

Handling Odd-Length Arrays

When n is odd, we cannot split exactly in half. The midpoint formula with integer division handles this naturally:

If n = 7 (left=0, right=6): mid = 0 + (6-0)/2 = 3
- Left subarray: [0..3] = 4 elements
- Right subarray: [4..6] = 3 elements

The left half gets the extra element. This asymmetry is fine—what matters is that both subproblems are strictly smaller than 7.

Midpoint Examples for Various Array Sizes
Array Size (n)	right	mid	Left Half Size	Right Half Size
8	7	3	4	4
7	6	3	4	3
6	5	2	3	3
5	4	2	3	2
4	3	1	2	2
3	2	1	2	1
2	1	0	1	1
1	0	—	Base case	—

Base Case Analysis: When Division Stops

Every recursive algorithm needs a termination condition. For merge sort's divide phase, the base case is when the subproblem is too small to divide further.

Base Case Condition

if left >= right:
    return  // Array of 0 or 1 elements is already sorted

This handles two scenarios:

left == right: Single-element subarray. One element is trivially sorted.
left > right: Empty subarray (can occur in some implementations). Zero elements are trivially sorted.

Why Not Check for left == right Only?

Some implementations use left == right as the base case. While this works for most inputs, using left >= right is more robust:

It handles empty ranges gracefully
It guards against bugs where right < left might occur due to errors elsewhere
It's no less efficient (one comparison either way)

Defensive Programming

Using >= instead of == is an example of defensive programming. The cost is negligible, but it prevents potential bugs from cascading. In production code, prefer conditions that fail safely.

Alternative Base Case: Early Termination for Small Arrays

In practice, many implementations use a larger base case for efficiency:

if right - left + 1 <= THRESHOLD:
    insertionSort(A, left, right)
    return

Where THRESHOLD might be 10-20 elements. This optimization works because:

Insertion sort has lower constant factors than merge sort
For small arrays, O(n²) with tiny n is faster than O(n log n) with recursion overhead
Fewer recursive calls means less call stack overhead

This is a hybrid algorithm optimization, but the conceptual divide phase remains the same—we're just choosing when to stop dividing.

Impact of Base Case Threshold on Performance
Threshold	Pure Merge Sort at Leaves	Total Recursive Calls (n=1000)	Practical Impact
1	Yes	~2000	Higher overhead, more calls
5-10	No (use insertion)	~200-500	Balanced, commonly used
20-30	No (use insertion)	~70-100	Good for cache efficiency
50+	No	~40+	Diminishing returns

Guaranteeing Progress: The Key to Termination

For merge sort to terminate, we must guarantee that every recursive call makes progress toward the base case. This means proving that both subproblems are strictly smaller than the original (for any non-base-case input).

Proof of Progress

Given: An array A[left..right] where left < right (i.e., at least 2 elements).

Let: mid = left + (right - left) / 2

Left Subproblem: [left..mid]

Size = mid - left + 1
Since mid ≥ left (because right > left implies (right-left)/2 ≥ 0)
Since mid < right (because (right-left)/2 < right-left when left < right)
Therefore, the left subproblem has size < original size ✓

Right Subproblem: [mid+1..right]

Size = right - (mid+1) + 1 = right - mid
Since mid ≥ left, we have mid+1 > left
Since mid+1 ≤ right (because mid < right)
Therefore, the right subproblem has size < original size ✓

Both subproblems are strictly smaller, so the recursion must terminate.

The Critical Inequality

The key inequality is: left ≤ mid < right. This ensures the left half gets at least 1 element (up to mid), and the right half gets at least 1 element (mid+1 to right). Without this guarantee, we could have empty or original-sized subproblems.

Common Bugs That Violate Progress

Several coding mistakes can break the progress guarantee:

Bug 1: Wrong Boundaries

mergeSort(A, left, mid)      // Correct: [left..mid]
mergeSort(A, mid, right)     // BUG: [mid..right] overlaps and can equal original

Fix: Use mid+1 for the right subproblem's start.

Bug 2: Inclusive vs. Exclusive Confusion

mid = left + (right - left) / 2    // If right is exclusive...
mergeSort(A, left, mid)            // [left..mid) - might be empty!
mergeSort(A, mid, right)           // [mid..right) - might equal original!

Fix: Be consistent with inclusive/exclusive conventions.

Bug 3: Wrong Midpoint Rounding

mid = left + (right - left + 1) / 2   // Rounds up instead of down
// For [0,1]: mid = 0 + (1-0+1)/2 = 1
// Left subarray: [0,1] - same as original! INFINITE LOOP

Fix: Always use floor division for the midpoint.

Implementation Patterns Across Languages

The divide phase is implemented slightly differently across languages, but the core logic remains the same. Understanding these variations helps when reading or writing merge sort in different contexts.

divide_phase.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def merge_sort(arr, left, right):
    """Merge sort with explicit divide phase."""
    # Base case: 0 or 1 elements
    if left >= right:
        return
    
    # DIVIDE: Compute midpoint (safe from overflow in Python)
    mid = left + (right - left) // 2  # // ensures integer division
    
    # CONQUER: Recursively sort both halves
    merge_sort(arr, left, mid)         # Left half: [left..mid]
    merge_sort(arr, mid + 1, right)    # Right half: [mid+1..right]
    
    # COMBINE: Merge the sorted halves
    merge(arr, left, mid, right)
 
 
# Note: Python integers have arbitrary precision, so overflow
# isn't a concern. But we use the safe formula for consistency
# and to build good habits for other languages.

Slice-Based vs. Index-Based

Some implementations use array slices instead of index ranges:

# Slice-based (creates new arrays)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])      # Creates new array
    right = merge_sort(arr[mid:])     # Creates new array
    return merge(left, right)         # Returns merged array

This is cleaner conceptually but uses O(n log n) total extra space (new arrays at each level) versus O(n) for the index-based approach with a single auxiliary array.

Index-Based for Production, Slice-Based for Learning

Slice-based implementations are excellent for understanding the algorithm—they make the "divide" operation explicit and visible. Index-based implementations are better for production—they use less memory and avoid unnecessary copying. Understand both!

Time and Space Complexity of the Divide Phase

Let's analyze the complexity of the divide phase in isolation:

Time Complexity: O(1)

The divide phase performs:

One comparison (base case check): O(1)
One subtraction, one division, one addition (midpoint): O(1)
Setting up two recursive calls: O(1)

Total: O(1) per recursive call.

Space Complexity: O(1)

The divide phase uses:

A few local variables (left, right, mid): O(1)
No additional data structures

Note: This doesn't count the call stack, which we analyze separately.

Contribution to Total Algorithm Complexity

Since divide is O(1) and we make O(n) total recursive calls (at most 2n-1 nodes in the recursion tree), the divide phase contributes O(n) to the total algorithm time.

However, this O(n) is dominated by the O(n log n) merge phase, so the divide phase is negligible in asymptotic analysis. But in practice, the constant factors matter—this is why the divide phase should be as simple as possible.

Complexity Breakdown by Phase
Phase	Per-Call Time	Total Calls	Total Time	Space Impact
Divide	O(1)	O(n)	O(n)	O(1) per call
Conquer	Recursive	O(n)	Overhead only	O(log n) stack depth
Combine	O(n)	O(log n) levels	O(n log n)	O(n) auxiliary array
Total	—	—	O(n log n)	O(n)

Recursion Depth and Stack Space

The recursion depth is O(log n) because we halve the problem at each level. Each stack frame uses O(1) space, so total stack space is O(log n). This is why merge sort's space complexity is O(n) (for the auxiliary array) + O(log n) (for the stack) = O(n).

Visualizing the Divide Phase

Let's trace through the divide phase for a concrete example. Consider sorting [38, 27, 43, 3, 9, 82, 10]:

Level 0 (Root)

Array: [38, 27, 43, 3, 9, 82, 10]
Left: 0, Right: 6
Mid: 0 + (6-0)/2 = 3
Split into: [38, 27, 43, 3] and [9, 82, 10]

Level 1 (First halves)

Left subtree:                    Right subtree:
[38, 27, 43, 3]                  [9, 82, 10]
Left: 0, Right: 3                Left: 4, Right: 6
Mid: 0 + 3/2 = 1                 Mid: 4 + 2/2 = 5
Split: [38, 27] | [43, 3]        Split: [9, 82] | [10]

Level 2 (Quarters)

[38, 27]    [43, 3]    [9, 82]    [10]
 L:0 R:1    L:2 R:3    L:4 R:5    L:6 R:6 (BASE CASE)
 Mid: 0      Mid: 2     Mid: 4
 [38]|[27]  [43]|[3]   [9]|[82]

Level 3 (Base cases)

[38] [27] [43] [3] [9] [82] [10]
 All base cases (single elements)

Observation: Perfect Halving

Notice how each split is as close to 50-50 as possible. With 7 elements, we get 4+3, then 2+2 and 2+1, and so on. This balanced splitting is what gives merge sort its O(log n) depth.

The Recursion Tree Structure

The divide phase creates a complete binary tree (or nearly complete for non-power-of-2 sizes):

                         [0..6]
                        /      \
                   [0..3]      [4..6]
                   /    \      /    \
               [0..1] [2..3] [4..5] [6]
               /   \  /   \  /   \
             [0]  [1][2]  [3][4]  [5]

Key properties:

Height = ⌈log₂(n)⌉ = 3 for n=7
Total nodes = 2n - 1 = 13 for n=7
Leaves (base cases) = n = 7
Internal nodes (divide operations) = n - 1 = 6

Summary and What's Next

We've thoroughly examined the divide phase of merge sort—an operation that seems trivial but contains important subtleties that affect correctness and efficiency.

Key Takeaways

•Division is logical, not physical: We compute boundaries, not create new arrays (in efficient implementations).
•Midpoint calculation matters: Use left + (right - left) / 2 to avoid integer overflow—a real bug in production code.
•Progress must be guaranteed: Both subproblems must be strictly smaller to ensure termination.
•Base cases handle tiny subproblems: Arrays of 0 or 1 elements are trivially sorted.
•O(1) per call, O(n) total: The divide phase is fast, dominated by the O(n log n) merge phase.
•Perfect halving yields O(log n) depth: This balanced recursion is key to merge sort's efficiency.

What's Next:

With the divide phase understood, we move to the conquer phase: the recursive sorting of each half. We'll examine how the recursion unfolds, the call stack's behavior, and how to reason about the correctness of recursive solutions.

Page Complete

You now understand the divide phase in depth—from safe midpoint calculation to progress guarantees to recursion tree structure. This foundation prepares you for understanding how the recursive conquer phase builds on the division we've established.