Bottom-up merge sort

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

        # 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(nums, buf, lo, mid, hi)

            # The buffer now contains the sorted runs for this pass.
            # Copying back keeps the caller's list as the main list.
            nums[:] = buf

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

        return nums

    def _merge_runs(
        self,
        nums: 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 nums[i] <= nums[j]:
                buf[k] = nums[i]
                i += 1
            else:
                buf[k] = nums[j]
                j += 1

            k += 1

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

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