Shifting

Shift elements right until the correct spot is found.

Full insertion sort

Full insertion sort uses an outer loop from 1 to n-1, performing shift-and-insert for each element.

At each outer loop step, the sorted part grows by one and the new element is placed in its correct position.

Best case

Insertion sort's best case is O(n) when the array is already sorted. In this case, the inner while loop never runs.

The worst case (reverse sorted array) is O(n^2) because the entire sorted part is shifted for each element.

Exercise Insertion sort

Write insertion_sort(arr). Place each element in its correct position. Print [1, 2, 3, 4, 5, 6] with print(insertion_sort([5, 2, 4, 6, 1, 3])).

Show example solution

def insertion_sort(arr):
    # Sort the array
    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 = j - 1
        arr[j + 1] = key
    return arr
print(insertion_sort([5, 2, 4, 6, 1, 3]))

Test yourself

Inner loop

Shifting uses a ____ loop.

Show answer

Shifting uses a while loop.

Shifting: match the terms

Outer loop

1 to n-1
Inner while

Shifts
Best

O(n)
Worst

O(n^2)
What is insertion sort in the best case?
- O(n)
- O(n log n)
- O(n^2)
- O(1)
Show answer

O(n) — The best case is O(n).

Next lesson: Placement

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies