Insertion sort

Problem¶

Implement stable insertion sort for a Python list.

Key trick¶

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

I 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.

Python solution¶

class sorting_insertion_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # `nums[:i]` is the sorted prefix.
        for i in range(1, len(nums)):
            val = nums[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 nums[j] > val:
                nums[j + 1] = nums[j]
                j -= 1

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

        return nums