Top-down merge sort

Problem¶

Implement recursive merge sort for a Python list.

Key trick¶

Recursively split the input into halves, then stably merge the sorted halves.

Trap¶

Choose from the left on equality for stability; linked lists also use \(O(\log n)\) recursion space.

Why is it interesting?¶

It guarantees stable \(O(n \log n)\) sorting and works especially well with linked lists.

Python solution¶

class sorting_merge_sort_top_down:
    def sort(self, nums: list[int]) -> list[int]:
        buf = [0] * len(nums)
        self._sort_range(nums, buf, 0, len(nums))
        return nums

    def _sort_range(self, nums, buf, lo, hi) -> None:
        # Ranges are half-open: `[lo, hi)`.

        if hi - lo <= 1:
            return

        mid = (lo + hi) // 2
        self._sort_range(nums, buf, lo, mid)
        self._sort_range(nums, buf, mid, hi)

        # Merge [lo, mid) and [mid, hi)
        i = lo  # `i` reads the left half
        j = mid # `j` reads the right half.
        k = lo

        while i < mid and j < hi:
            # Choose the left value on equality to preserve stability.
            if nums[i] <= nums[j]:
                buf[k] = nums[i]
                i += 1
            else:
                buf[k] = nums[j]
                j += 1

            k += 1

        while i < mid:
            buf[k] = nums[i]
            i += 1
            k += 1

        while j < hi:
            buf[k] = nums[j]
            j += 1
            k += 1

        nums[lo:hi] = buf[lo:hi]