Bottom-up merge sort linked list

class sorting_merge_sort_bottom_up_linked_list:
    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