Top-down merge sort

class sort_merge_sort_top_down:
    def sort(self, nums: list[int]) -> list[int]:
        # `arr` is the result; `buf` is reused by every merge.
        arr = nums[:]
        buf = [0] * len(arr)

        self._sort_range(arr, buf, 0, len(arr))
        return arr

    def _sort_range(
        self,
        arr: list[int],
        buf: list[int],
        lo: int,
        hi: int,
    ) -> None:
        # Ranges are half-open: `[lo, hi)`.
        # Empty and one-element ranges are already sorted.
        if hi - lo <= 1:
            return

        mid = (lo + hi) // 2

        # Recursively sort both halves before merging them.
        self._sort_range(arr, buf, lo, mid)
        self._sort_range(arr, buf, mid, hi)

        self._merge(arr, buf, lo, mid, hi)

    def _merge(
        self,
        arr: list[int],
        buf: list[int],
        lo: int,
        mid: int,
        hi: int,
    ) -> None:
        # `i` reads the left half and `j` reads the right half.
        i = lo
        j = mid
        k = lo

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

            k += 1

        # At most one of these loops copies any values.
        while i < mid:
            buf[k] = arr[i]
            i += 1
            k += 1

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

        # Copy the merged range back into the main list.
        arr[lo:hi] = buf[lo:hi]

class sort_merge_sort_linked_top_down:
    def sort(
        self,
        head: ListNode | None,
    ) -> ListNode | None:
        # Empty and one-node lists are already sorted.
        if head is None or head.next is None:
            return head

        # Find the midpoint with the slow/fast-pointer pattern.
        # Starting `fast` one node ahead leaves `slow` at the end
        # of the left half.
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Split the list into two independent lists.
        r = slow.next
        slow.next = None

        # Sort each half and merge their nodes.
        l = self.sort(head)
        r = self.sort(r)

        return self._merge_linked(l, r)

    def _merge_linked(
        self,
        l: ListNode | None,
        r: ListNode | None,
    ) -> ListNode | None:
        # The dummy node removes special handling for the result's head.
        dummy = ListNode()
        tail = dummy

        while l and r:
            # Take from the left on equality to preserve stability.
            if l.val <= r.val:
                tail.next = l
                l = l.next
            else:
                tail.next = r
                r = r.next

            tail = tail.next

        # The remaining list is already sorted, so attach it directly.
        tail.next = l if l else r

        return dummy.next