DSA Sorting Exercises

Your brief

Use the course’s stable merge implementation with observation counts as keys and names as identities. Two equal-count records begin in a known order. The exercise checks their returned order and that the original input list remains unchanged. It deliberately reuses the actual authored function rather than copying its logic into the test. Stability is not required by every sort, but it must be verified when the interface promises it.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as exercises.py and run python exercises.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Worked solution

def merge_sort(values, key=lambda item: item):
    if len(values) < 2:
        return list(values)
    middle = len(values) // 2
    left = merge_sort(values[:middle], key)
    right = merge_sort(values[middle:], key)
    result = []
    a = b = 0
    while a < len(left) and b < len(right):
        if key(left[a]) <= key(right[b]):
            result.append(left[a])
            a += 1
        else:
            result.append(right[b])
            b += 1
    result.extend(left[a:])
    result.extend(right[b:])
    return result

records = [(4, "oak"), (2, "gate"), (4, "pond")]
before = list(records)
result = merge_sort(records, key=lambda record: record[0])
assert records == before
assert [name for _, name in result] == ["gate", "oak", "pond"]
print(result)

[(2, 'gate'), (4, 'oak'), (4, 'pond')]

Time, space and assumptions

This reused merge sorter takes O(n log n) comparisons and O(n) peak list storage under its documented model. The additional fixture assertions inspect O(n) result and input values.

Extend and test

Add repeated keys with distinct labels, an empty list and a reverse-ordered list. Check sorted keys, complete record preservation, stable ties and unchanged input.