Merge sort

What is sorting?

Sorting puts values in an order, usually smallest to largest. Different sorting algorithms move and compare values in different ways, so their time and memory costs differ. Selection is a related task: finding a particular ranked value, such as the third smallest, without necessarily sorting everything.

Example: Sorting [8, 2, 5] gives [2, 5, 8]. The second smallest value is 5. If records have equal sort keys, a stable sort keeps their original relative order.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Recursion

Understand the idea

Merge sort recursively sorts two halves and merges them. The merge pointer invariant is easier to prove than a whole-array claim. Splitting creates logarithmic levels; each level processes linear total data.

Work through an example

[4,1,3,2] splits to singletons, merges into [1,4] and [2,3], then [1,2,3,4]. Remaining tails can be appended after one side ends.

Time and space complexity

Θ(n log n) time/O(n) peak extra space for this slicing implementation; cumulative allocations can be larger than peak.

Why it works

The output is sorted and contains exactly the smallest consumed elements from both halves.

Common mistakes

Missing the remaining tail drops elements.
A base case must return an independent result if promised.

Chapter lab · Python implementation

Sorting makes order-dependent reasoning possible but adds preprocessing cost. The lab implements stable merge sort and a simple partition-based selection baseline. Compare them with in-place quickselect, counting/radix methods, and small-input insertion sort. Stability means preserving the original order of records with equal sort keys.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def merge_sort(values):
    if len(values)<2:
        return values.copy()
    middle=len(values)//2
    left=merge_sort(values[:middle])
    right=merge_sort(values[middle:])
    merged=[]
    i=j=0
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            merged.append(left[i]); i+=1
        else:
            merged.append(right[j]); j+=1
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged

def select(values,k):
    if not 0<=k<len(values):
        raise ValueError('invalid rank')
    pivot=values[len(values)//2]
    lower=[x for x in values if x<pivot]
    equal=[x for x in values if x==pivot]
    higher=[x for x in values if x>pivot]
    if k<len(lower):
        return select(lower,k)
    if k<len(lower)+len(equal):
        return pivot
    return select(higher,k-len(lower)-len(equal))

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert merge_sort([3,1,2,1])==[1,1,2,3]
assert merge_sort([])==[]
assert all(select([5,1,5,2,9],k)==sorted([5,1,5,2,9])[k] for k in range(5))

CHECK YOUR UNDERSTANDING