Placement

Place the element in the gap and sort the whole array.

Insertion sort advantages

Insertion sort is very efficient for small or nearly sorted arrays. Since the best case is O(n), it is fast on nearly sorted data.

It also sorts in-place: no extra memory is needed. This is advantageous in memory-constrained systems.

Complexity comparison

Insertion sort has the same O(n^2) complexity as bubble sort and selection sort, but is faster in practice because it does fewer writes.

On nearly sorted arrays, insertion sort is O(n) while bubble sort and selection sort are still O(n^2).

Exercise Insertion step

Write insertion_step(arr, i). Shift the i-th element into the sorted part. Print [2, 3, 4, 6] with print(insertion_step([2, 4, 6, 3], 3)).

Show example solution

def insertion_step(arr, i):
    # Do one step
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j = j - 1
    arr[j + 1] = key
    return arr
print(insertion_step([2, 4, 6, 3], 3))

Test yourself

Placement: match the terms

Insertion sort

Nearly sorted
Best

O(n)
In-place

No extra memory
Few writes

Fast in practice
On which arrays is insertion sort fastest?
- Reverse sorted
- Random
- Nearly sorted
- Very large
Show answer

Nearly sorted — Fastest on nearly sorted arrays.

In-place sorting

Insertion sort requires ____ extra memory.

Show answer

Insertion sort requires little extra memory.

Next lesson: Summary - Insertion sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies