🎓 A1Learner
🔍

DSA Insertion Sort

Insertion sort is a sorting method that slides each new value into its place. The values before the new one always stay in sorted order.

Sliding one value in

The sorted part is the part already in order. The new value slides left until a smaller value stops it.

data = [2, 5, 9]
value = 4
data.append(value)
i = len(data) - 2
while i >= 0 and data[i] > value:
    data[i + 1] = data[i]
    i -= 1
data[i + 1] = value
print(data)

Counting the shifts

A shift is one value moving one place to the right. The shift count shows how much work each list makes the sort do.

def insertion_shifts(values):
    data = values[:]
    shifts = 0
    for i in range(1, len(data)):
        value = data[i]
        j = i - 1
        while j >= 0 and data[j] > value:
            data[j + 1] = data[j]
            shifts += 1
            j -= 1
        data[j + 1] = value
    return shifts

print("nearly sorted shifts:", insertion_shifts([1, 2, 3, 5, 4]))
print("reversed shifts:", insertion_shifts([5, 4, 3, 2, 1]))

The sorted part grows

Each round takes the next value from the unsorted part. The printed list shows the sorted part growing by one value per round.

data = [3, 1, 2]
for i in range(1, len(data)):
    value = data[i]
    j = i - 1
    while j >= 0 and data[j] > value:
        data[j + 1] = data[j]
        j -= 1
    data[j + 1] = value
    print(data)

Example

def insertion_sort(values):
    data = values[:]
    total = 0
    for i in range(1, len(data)):
        value = data[i]
        shifts = 0
        j = i - 1
        while j >= 0 and data[j] > value:
            data[j + 1] = data[j]
            shifts += 1
            j -= 1
        data[j + 1] = value
        total += shifts
        print("placed", value, "shifts:", shifts, "list:", data)
    print("total shifts:", total)
    return data

result = insertion_sort([12, 19, 23, 27, 31, 35, 30, 42])
print("sorted:", result)

Key points

  • Insertion sort grows a sorted part at the left of the list.
  • Nearly sorted data needs very few shifts per value.
  • Fully reversed data forces every value to shift past all earlier values.

In this example, insertion sort runs on a list where only the value 30 sits out of place. Every other value is already past its correct spot, so it shifts zero times. The value 30 slides past 35 and 31, which costs two shifts in total. The whole list of eight values is sorted after just two shifts.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Insertion sort runs on a list that is already fully sorted. How many shifts does it make?