This lesson's interactive features are locked, please to keep using them

Why Use Insertion Sort?

Fast: for very small data sets (even faster than merge sort and quick sort, which we'll cover later)
Adaptive: Faster for partially sorted data sets
Stable: Does not change the relative order of elements with equal keys
In-Place: Only requires a constant amount of memory
Online: Can sort a list as it receives it

Why Is Insertion Sort Fast for Small Lists?

Many production sorting implementations use insertion sort for very small inputs under a certain threshold (very small, like 10-ish), and switch to something like quicksort for larger inputs. They use insertion sort because:

There is no recursion overhead
It has a tiny memory footprint
It's a stable sort as described above

Reference

def insertion_sort(nums: list[int]) -> list[int]:
    for i in range(len(nums)):
        j = i
        while j > 0 and nums[j - 1] > nums[j]:
            nums[j], nums[j - 1] = nums[j - 1], nums[j]
            j -= 1
    return nums