Bottom-up merge sort

class sort_merge_sort_bottom_up:
    def sort(self, nums: list[int]) -> list[int]:
        arr = nums[:]
        n = len(arr)

        # Each pass writes merged runs into the other list.
        buf = [0] * n

        # Runs of width one are already sorted.
        width = 1

        while width < n:
            # Merge adjacent runs:
            # `[lo, mid)` with `[mid, hi)`.
            for lo in range(0, n, 2 * width):
                mid = min(lo + width, n)
                hi = min(lo + 2 * width, n)

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

            # The buffer now contains the sorted runs for this pass.
            # Swapping references avoids copying the whole list.
            arr, buf = buf, arr

            # Each new run combines two runs from the previous pass.
            width *= 2

        return arr

    def _merge_runs(
        self,
        arr: list[int],
        buf: list[int],
        lo: int,
        mid: int,
        hi: int,
    ) -> None:
        i = lo
        j = mid
        k = lo

        # Merge the two runs into `buf`.
        while i < mid and j < hi:
            # Choosing the left value on equality makes this stable.
            if arr[i] <= arr[j]:
                buf[k] = arr[i]
                i += 1
            else:
                buf[k] = arr[j]
                j += 1

            k += 1

        # Copy the unconsumed part of either run.
        while i < mid:
            buf[k] = arr[i]
            i += 1
            k += 1

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

class sort_merge_sort_linked_bottom_up:
    def sort(
        self,
        head: ListNode | None,
    ) -> ListNode | None:
        # The length determines how many run sizes must be merged.
        n = 0
        cur = head

        while cur:
            n += 1
            cur = cur.next

        # The dummy node makes replacement of the head straightforward.
        dummy = ListNode(next=head)

        # One-node runs are initially sorted.
        width = 1

        while width < n:
            # Rebuild the list from merged runs during this pass.
            prev = dummy
            cur = dummy.next

            while cur:
                # Cut out two adjacent runs of at most `width` nodes.
                l = cur
                r = self._split_run(l, width)
                cur = self._split_run(r, width)

                # Merge the detached runs, then attach them to the result.
                merged_head, merged_tail = self._merge_runs(l, r)
                prev.next = merged_head
                prev = merged_tail

            # Each pass doubles the size of sorted runs.
            width *= 2

        return dummy.next

    def _split_run(
        self,
        head: ListNode | None,
        size: int,
    ) -> ListNode | None:
        """Cut after at most `size` nodes and return the following run."""

        if head is None:
            return None

        # Stop at the final node belonging to this run.
        for _ in range(size - 1):
            if head.next is None:
                break

            head = head.next

        # Detach this run from the rest of the list.
        nxt = head.next
        head.next = None

        return nxt

    def _merge_runs(
        self,
        l: ListNode | None,
        r: ListNode | None,
    ) -> tuple[ListNode | None, ListNode]:
        # Return both ends because the caller must append another merged run.
        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

        # Attach the unconsumed run without copying its nodes.
        tail.next = l if l else r

        # Find the actual tail required by the outer merge loop.
        while tail.next:
            tail = tail.next

        return dummy.next, tail