2.3.1 - Merge sort and quicksort

Merge by selecting the smallest remaining head

Merging combines two already sorted lists into one sorted list. Keep a position at the first unused item in each list. Compare these two heads, append the smaller one, and advance only that list's position. Its next item becomes the new head. When a list is exhausted, append all unused items of the other list in their existing order.

Merge [2,6,9] and [1,6,8] in ascending order. Our tie rule selects from the left list when heads are equal. Labels 6L and 6R distinguish equal-key records; they are not part of the numeric comparison.

Selecting the smallest head works because nothing later in either sorted list can be smaller than its head. Do not repeatedly search the entire list for its minimum, sort each pair separately, or discard one equal value. Merging retains every item. Selecting the left head on equality preserves the original order of ties when the left and right sublists came from consecutive halves of the original list.

For lists with a total of n items, at most n-1 head comparisons are needed when both lists are nonempty; remaining items need copying but no further head comparisons. Time is $O(n)$. Empty plus nonempty input is just the nonempty list copied; two empty lists give an empty result.

Split first and sort during the merges

Merge sort divides a list into smaller consecutive halves until each has at most one item. Such a list is already sorted. It then merges sorted results on the way back through the recursion. Splitting alone does no sorting; the head comparisons during merging establish order.

For odd lengths, our split uses mid = length // 2: the left half gets the earlier mid items and the right half gets the rest. Here is the complete split and return sequence for [7,2,6,1,5]:

Split [7,2,6,1,5] into [7,2] and [6,1,5]
Split [7,2] into [7] and [2]
Merge [7] with [2] -> [2,7]
Split [6,1,5] into [6] and [1,5]
Split [1,5] into [1] and [5]
Merge [1] with [5] -> [1,5]
Merge [6] with [1,5] -> [1,5,6]
Merge [2,7] with [1,5,6] -> [1,2,5,6,7]

The left recursive call completes before the right begins in the shown implementation. Different evaluation orders can produce a different chronological trace, so state the convention when tracing. The final merge receives sorted [2,7] and [1,5,6], not the original unsorted halves.

Balanced splitting gives about $\log_2 n$ levels. Across one merge level, every item is copied into a result, giving $O(n)$ work per level. Standard merge sort therefore takes $O(n\log n)$ best, average and worst time for growing n. This version still splits and copies already sorted input; it has no special sorted-input shortcut.

Implement a complete merge and stopping case

A merge implementation tracks which values have already been consumed and copies both possible tails. The following functions take lists of comparable values and return a new ascending list without modifying their inputs. Ties choose the left head.

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(values):
    if len(values) <= 1:
        return values.copy()
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    return merge(left, right)

data = [7, 2, 6, 1, 5]
print(merge_sort(data))
print(data)

[1, 2, 5, 6, 7]
[7, 2, 6, 1, 5]

The loop uses and: both heads must exist for a comparison. or would allow an access into an exhausted list. Advancing neither index would repeat forever; advancing both after every choice would lose an unselected head. After the loop, at least one tail is empty, but the other may contain values. The base case includes length zero, avoiding repeatedly splitting an empty list.

OCR-style pseudocode can use a fixed output array instead of Python's growing list. Here leftN and rightN are the input lengths; k is the next output position. This complete merge uses inclusive for conventions elsewhere but only guarded while loops here:

function merge(left, leftN, right, rightN)
    array output[leftN + rightN]
    i = 0
    j = 0
    k = 0
    while i < leftN AND j < rightN
        if left[i] <= right[j] then
            output[k] = left[i]
            i = i + 1
        else
            output[k] = right[j]
            j = j + 1
        endif
        k = k + 1
    endwhile
    while i < leftN
        output[k] = left[i]
        i = i + 1
        k = k + 1
    endwhile
    while j < rightN
        output[k] = right[j]
        j = j + 1
        k = k + 1
    endwhile
    return output
endfunction

The essential algorithm is to merge already sorted portions, not to call a built-in sort. Merge sort supplies this operation with the recursively sorted halves described in the previous part.

Explore one head at a time

Predict the first selected record and the final equal-key order, then run this ungraded merge. The tuples carry (key, label), but the comparison reads only the key. After the compared-head loop, the output still needs any unread tail.

For this sequential list-based version, peak auxiliary list storage is $O(n)$: retained halves, returned sublists and merge results have a total bounded by a constant multiple of n. The call stack has $O(\log n)$ frames. Slicing creates additional copying, and total allocation over the whole run is $O(n\log n)$; that is different from peak live storage. An implementation using one reusable merge buffer also needs $O(n)$ auxiliary space. Do not label standard array merge sort constant-space.