Insertion sort

Problem¶

Implement stable insertion sort for Python lists and singly linked lists.

Key trick¶

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

Both versions take \(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¶

Python list¶

class sort_insertion_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Preserve the caller's input.
        arr = nums[:]

        # `arr[:i]` is the sorted prefix.
        for i in range(1, len(arr)):
            val = arr[i]
            j = i - 1

            # Shift larger elements right to open an insertion position.
            # Using `>` rather than `>=` preserves the order of equal values.
            while j >= 0 and arr[j] > val:
                arr[j + 1] = arr[j]
                j -= 1

            # Insert the saved value into the resulting gap.
            arr[j + 1] = val

        return arr

Singly linked list¶

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