Taking From the Right Half on a Tie

Comparing with < instead of <= moves equal keys out of their input order.

Merge sort is stable only if its merge takes from the left half when the two front items are equal, so the comparison must be <=, not <. This card shows the symptom of getting that one character wrong, why it happens, what it costs, and the fix.

The symptom is a sort whose output looks right. Four student records, in input order Ana 80, Ben 75, Cai 80 and Dee 75, are sorted by grade. Every 75 comes out before every 80, as it should, but within each grade the names come out in reverse of their input order. No error, no wrong grade, nothing a test on the grades alone would catch. The listing below sorts the records twice, once with each comparison, and labels each record with its position in the input.

tie_records.pypy

records = [("Ana", 80), ("Ben", 75), ("Cai", 80), ("Dee", 75)]
position = {name: index for index, (name, _) in enumerate(records, start=1)}


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


def merge_sort(items, takes_left):
    if len(items) < 2:
        return items
    mid = len(items) // 2
    return merge(merge_sort(items[:mid], takes_left), merge_sort(items[mid:], takes_left), takes_left)


for label, takes_left in [("<", lambda a, b: a < b), ("<=", lambda a, b: a <= b)]:
    result = merge_sort(records, takes_left)
    print(f"with {label}:", ", ".join(f"{name} {grade} (input {position[name]})" for name, grade in result))
print("built-in sorted:", ", ".join(f"{name} {grade}" for name, grade in sorted(records, key=lambda record: record[1])))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

with <: Dee 75 (input 4), Ben 75 (input 2), Cai 80 (input 3), Ana 80 (input 1)
with <=: Ben 75 (input 2), Dee 75 (input 4), Ana 80 (input 1), Cai 80 (input 3)
built-in sorted: Ben 75, Dee 75, Ana 80, Cai 80

The trigger is the comparison in the merge. With <, two equal grades make left < right false, so the merge falls into the other branch and takes the record from the right half. Every record in the right half came later in the input than every record in the left half, so on each tie the later record jumps ahead of the earlier one. With <=, a tie takes from the left, and the earlier record stays first.

The four records after sorting by grade, with each comparison
Output position	With <	With <=
1	Dee 75, input 4	Ben 75, input 2
2	Ben 75, input 2	Dee 75, input 4
3	Cai 80, input 3	Ana 80, input 1
4	Ana 80, input 1	Cai 80, input 3

The cost appears as soon as anything relies on stability. A common way to sort by two keys is to sort by the second key first and then by the first key, trusting the second sort to keep the order of the first among equal values. The four records went in already in name order, so the run above is that second sort: with <, Dee lands before Ben and Cai before Ana, and the name order the first sort produced is gone. The bug cannot be seen on plain numbers, where equal values are indistinguishable, which is how it survives: the tests pass on integers, and the records go wrong in production.

The remedy is <= in the merge, and a test that sorts records with equal keys and checks their order. Python's sorted, which printed the same order as the <= merge, is guaranteed stable, as are Java's Arrays.sort on objects and JavaScript's Array.prototype.sort since ES2019. A hand-written merge sort carries the guarantee only if its merge does.

On the Algorithms: Efficient Sorting cheatsheet

← → move through sections and cards