Insertion sort idea

Like sorting cards, insert each element into the sorted left part.

Insertion sort logic

Insertion sort takes each element and places it in its correct position within the sorted part. This is like arranging cards in your hand.

Initially, the first element is considered sorted. Then the second is taken and placed correctly relative to the first. This repeats for all elements.

Shifting

When placing an element, you shift the sorted elements that are larger than it one step to the right. This makes room for the new element.

Shifting moves elements one by one to the right. The new element goes into the freed slot. This involves fewer writes than swapping.

Exercise Shift and insert

Write insert_in_place(arr, i). Place arr[i] in the sorted part. Print [1, 2, 3, 5] with print(insert_in_place([1, 3, 5, 2], 3)).

Show example solution

def insert_in_place(arr, i):
    # Insert in place
    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(insert_in_place([1, 3, 5, 2], 3))

Test yourself

What is insertion sort compared to?
- Tree traversal
- Binary search
- Hash computing
- Arranging cards
Show answer

Arranging cards — It is compared to arranging cards.

Sorted part

The first ____ element is considered sorted.

Show answer

The first 1 element is considered sorted.

Insertion sort idea: match the terms

Insertion sort

Place correctly
Shifting

Move right
Sorted part

At the start
O(n^2)

Worst

Next lesson: Shifting

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies