Module 15 · Recursion and Divide-and-Conquer

146. Merge Sort

Bridge · Download this solution · All solutions and shared helpers

Problem

Return a stable nondecreasing copy of an integer list using merge sort. Leave the input unchanged. Empty and singleton lists return new lists with the same values. Stability means equal values retain source order when carrying records with keys.

Examples

Example 1

merge_sort([4,1,3,2])
=> [1, 2, 3, 4]

Sorted child results are merged.

Example 2

merge_sort([])
=> []

The empty list is a base case.

Example 3

merge_sort([2,1,2])
=> [1, 2, 2]

Multiplicity is preserved across the split.

Reveal the worked solution and reasoning

Why this mechanism works

A call promises a sorted version of its entire input segment. Divide into two smaller segments, let each recursive call fulfill that promise, then combine them with the stable two-frontier merge from kata 021. The merge is valid because the recursive results are already sorted.

State and boundaries

left and right are complete sorted child results. mid defines the split; neither child includes the other's positions.

Protocol

Return a copy for length<=1.
Split at the midpoint.
Recursively sort both halves.
Merge the two sorted results stably.
Return the merged list.

Visualization

[4,1,3,2]
[4,1] | [3,2]
[1,4] | [2,3]
merge -> [1,2,3,4]

Python implementation

from kata_021 import merge_sorted

def merge_sort(nums):
    if len(nums) <= 1:
        return list(nums)
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge_sorted(left, right)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

merge_sort([4,1,3,2])

L4 merge_sort: if len(nums) <= 1:
nums=[4, 1, 3, 2]

L6 merge_sort: mid = len(nums) // 2
nums=[4, 1, 3, 2]; mid=2

L4 merge_sort: if len(nums) <= 1:
nums=[4, 1]

L6 merge_sort: mid = len(nums) // 2
nums=[4, 1]; mid=1

L4 merge_sort: if len(nums) <= 1:
nums=[4]

L7 merge_sort: left = merge_sort(nums[:mid])
nums=[4, 1]; mid=1; left=[4]

L4 merge_sort: if len(nums) <= 1:
nums=[1]

L8 merge_sort: right = merge_sort(nums[mid:])
nums=[4, 1]; mid=1; left=[4]; right=[1]

... 4 intermediate state changes omitted ...

L7 merge_sort: left = merge_sort(nums[:mid])
nums=[3, 2]; mid=1; left=[3]

L4 merge_sort: if len(nums) <= 1:
nums=[2]

L8 merge_sort: right = merge_sort(nums[mid:])
nums=[3, 2]; mid=1; left=[3]; right=[2]

L8 merge_sort: right = merge_sort(nums[mid:])
nums=[4, 1, 3, 2]; mid=2; left=[1, 4]; right=[2, 3]

Result: [1, 2, 3, 4]. Sorted child results are merged.

merge_sort([])

L4 merge_sort: if len(nums) <= 1:
nums=[]

Result: []. The empty list is a base case.

Why the solution is correct

Singletons and empty lists are sorted. Assuming each smaller call returns a sorted permutation of its input, stable merge returns a sorted permutation of both halves together while preserving equal-key order. Induction on input length establishes the result.

Time and space

O(n log n) time and O(n) peak auxiliary storage for slices and merged results, plus O(log n) call depth.

Common mistakes

Merging before the child calls finish violates the merge precondition. A non-strict equality choice in the wrong direction can break stability for records.

Reasoning card

State: left and right are complete sorted child results. mid defines the split; neither child includes the other's positions.

Invariant: Each call returns a sorted permutation of its input slice.

Decision to rehearse: Combine two sorted child results.

Finish: Return the merged list

Transfer exercise

Count inversions during merging: when a right value is chosen before remaining left values, how many inversions does it create?