Implement Merge Sort and QuickselectStep 5 of 5

Stable sort by key

12345

Step 5: Stable sort by key

Real data is usually records ordered by a field: sort users by age, orders by date. When two records share a key, a STABLE sort keeps them in their original relative order, critical when you sort by one field after another.

Write sort_by_key(items, key) that returns a NEW list of items sorted by key(item) in ascending order, stably. Do not mutate items.

Reuse the merge-sort idea from Step 2, but compare by key(item) instead of the value itself. On a tie between the left and right halves, take from the LEFT half first. That is exactly what preserves stability.

Hints
Starter code
def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result


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


def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i


def quick_sort(arr):
    work = list(arr)

    def _qs(lo, hi):
        if lo < hi:
            p = partition(work, lo, hi)
            _qs(lo, p - 1)
            _qs(p + 1, hi)

    _qs(0, len(work) - 1)
    return work


def quickselect(arr, k):
    work = list(arr)
    lo, hi = 0, len(work) - 1
    while True:
        if lo == hi:
            return work[lo]
        p = partition(work, lo, hi)
        if p == k:
            return work[p]
        elif p < k:
            lo = p + 1
        else:
            hi = p - 1


def sort_by_key(items, key):
    """Stable sort of items by key(item), preserving order among equal keys."""
    # TODO: merge-sort on key(item); on ties, take from the left half first.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges