Skip to content

Insertion sort linked list

Problem

Implement stable insertion sort a singly linked list.

Key trick

Maintain a sorted prefix and insert each new element into its correct position.

It takes \(O(n^2)\) time in the worst case and \(O(1)\) auxiliary space.

Trap

For stability, insert a new equal element after existing equal elements.

Why is it interesting?

It is excellent for small or nearly sorted inputs and works naturally by relinking linked-list nodes.

Python solution

class sorting_insertion_sort_linked_list:
    def sort(
        self,
        head: ListNode | None,
    ) -> ListNode | None:
        # `dummy.next` is the head of the independently built sorted list.
        dummy = ListNode()
        cur = head

        while cur:
            # Save the next unsorted node before changing `cur.next`.
            nxt = cur.next

            # Find the node after which `cur` should be inserted.
            prev = dummy

            # Move past equal values to preserve their original order.
            while prev.next and prev.next.val <= cur.val:
                prev = prev.next

            # Insert `cur` between `prev` and `prev.next`.
            cur.next = prev.next
            prev.next = cur

            cur = nxt

        return dummy.next