Python merge sort: stable ordering without editing the input

Operation contract

The receipt sorter accepts a bounded list of integer amount and string ID pairs. During merge it takes an equal-key entry from the left run first, preserving the input order of equal amounts. The caller’s list remains unchanged. This stability is useful when a previous import order carries meaning that should survive amount-based sorting.

Failure and ownership boundary

The fixture caps input at 128 records and rejects booleans as amounts. A comparison function with side effects or inconsistent ordering would invalidate the proof. Production Python already provides a stable built-in sort; this program teaches merge mechanics rather than recommending a replacement. Python sorting: stable keys, independent output and explicit tie rules defines the practical default.

Working program

def sort_receipts(receipts):
    if len(receipts) > 128 or any(type(amount) is not int or type(identifier) is not str for amount, identifier in receipts):
        raise ValueError("bounded receipt pairs required")
    def sort_run(records):
        if len(records) < 2:
            return records.copy()
        middle = len(records) // 2
        left, right = sort_run(records[:middle]), sort_run(records[middle:])
        merged, left_index, right_index = [], 0, 0
        while left_index < len(left) and right_index < len(right):
            if left[left_index][0] <= right[right_index][0]:
                merged.append(left[left_index]); left_index += 1
            else:
                merged.append(right[right_index]); right_index += 1
        return merged + left[left_index:] + right[right_index:]
    return sort_run(receipts)

receipts = [(125, "R41"), (75, "R42"), (125, "R43")]
print(sort_receipts(receipts))
print(receipts)

Output

[(75, 'R42'), (125, 'R41'), (125, 'R43')]
[(125, 'R41'), (75, 'R42'), (125, 'R43')]

Costs and limits

The implementation performs O(n log n) comparisons and copied references, with O(n) peak auxiliary entries plus O(log n) call depth. Slicing and intermediate list concatenation add allocation work.

Common Mistakes

• Choosing the right run on equal keys would change stability.
• Use the built-in sort when implementing an application rather than studying the algorithm.

Connected lessons

Python sorting: stable keys, independent output and explicit tie rules, Python binary search: use a half-open interval and require sorted input, Python shallow and deep copies: preserve aliases deliberately.

Trace the related workflow

Python exercise: merge two sorted feeds and preserve left-first ties.