Algorithm Guidecomplexity: O(n²)

Insertion Sort

Compares each element against the already-sorted portion and inserts it into the right position. Remarkably fast when the data is nearly sorted.

01Insertion Sort

Explore How It Works

Starting insertion sort. Pick up one value at a time and slot it into the sorted run on the left. The leading 45 counts as already sorted.

Pick up 12. Look through the sorted run on the left for where it belongs.

45 on the left is larger than 12. Shift it one slot right to make room.

There is nothing more to check on the left. Put 12 down in the empty first slot.

Pick up 89. It is larger than the 45 at the end of the run, so nothing shifts and it stays put.

Pick up 34. Find its place among the sorted 12 · 45 · 89.

Both 89 and 45 are larger than 34. Shift each of them one slot right.

Stop at 12. It is smaller than 34, so put 34 down in the empty slot just after it.

Pick up 67. Shifting 89 alone opens the slot where 67 belongs.

Pick up 23. Shift 89 · 67 · 45 · 34 in turn and put it down just after 12.

Pick up 56. Shift 89 and 67, then put it down just after 45.

Pick up the last value, 10. It is the smallest, so everything shifts and it lands at the front.

Insertion sort is done. On an already-nearly-sorted array there is little to shift, which makes it especially fast.

Live Python

1def insertion_sort(arr):

# start from i: 1

2 for i in range(1, len(arr)):

3 key = arr[i]

4 j = i - 1

5 while j >= 0 and arr[j] > key:

6 arr[j + 1] = arr[j]

7 j -= 1

8 arr[j + 1] = key

9 return arr

1 / 13

02 Understand It Simply

For Everyone

🔑How It Works

Treats the front as sorted and slots the next value into its place within it. Especially fast on nearly-sorted data.

💡In Plain Words

Treats the front as already sorted and pushes each new value into position.

Very fast on nearly-sorted data.

📍Where It's Used

–Small or nearly-sorted data
–the finishing step of other sorts

03 Python Implementation

A clean, readable reference implementation of the core logic of Insertion Sort.

core_implementation.py

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

04 Frequently Asked Questions

FAQ

What is Insertion Sort?+

Compares each element against the already-sorted portion and inserts it into the right position. Remarkably fast when the data is nearly sorted.

What is the time complexity of Insertion Sort?+

The time complexity of Insertion Sort is O(n²). Follow the step-by-step visualization to see exactly why.

Where is Insertion Sort used?+

Small or nearly-sorted data, the finishing step of other sorts.

What's a simple analogy for Insertion Sort?+

Treats the front as sorted and slots the next value into its place within it. Especially fast on nearly-sorted data.

→ Sorting — see allRelated