Insertion Sort

The Idea

Treat the left side as already sorted and pick up the next element. Shift the bigger values one slot right until a gap opens, then drop it in. Generally O(n²), but close to O(n) on nearly sorted data.

Real-World Example

A barista clips order tickets onto a rail kept in pickup-time order. A new ticket slides past the later ones until it finds its slot, usually only a step or two, because it is typically the latest anyway.

The Code

def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        # slide bigger values one slot to the right
        while j >= 0 and nums[j] > key:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key      # drop key into the gap
    return nums
# insertion_sort([7, 3, 9, 3]) -> [3, 3, 7, 9]

nums = [2, 5, 9, 0]
key, j = 4, 2
while j >= 0 and nums[j] > key:
  nums[j + 1] = nums[j]
  j -= 1
nums[j + 1] = key
print(nums)