Sorting

Foundation drill for this topic

Drill #29 — Insertion sort

Easy Shift & Place

In plain English: Sort a list by repeatedly picking the next element and inserting it into its correct spot.

Builds the sorted portion one element at a time by shifting — efficient for nearly-sorted data because few shifts are needed.

Prompt

Sort an array using insertion sort.

Try to write it from scratch before scrolling down.

Solution

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j &gt;= 0 and a[j] &gt; key:  # shift larger elements right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

# Test: insertion_sort([5,3,1,4,2]) == [1,2,3,4,5]

O(n^2) time · O(1) space · Stable

Related Micro Drills

Quick recall drills to reinforce this pattern.

87 Move zeros to end Pointer Manipulation 10s

Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.

w = 0
for r in range(len(a)):
    if a[r] != 0:
        a[w] = a[r]
        w += 1
while w &lt; len(a):
    a[w] = 0
    w += 1

126 Remove duplicates in-place Pointer Manipulation 10s

Write-pointer compaction for sorted arrays. Returns new length.

w = 1
for i in range(1, len(a)):
    if a[i] != a[i-1]:
        a[w] = a[i]
        w += 1
return w

73 Sort with key function Divide & Conquer 5s

Custom key sorting is Python's primary sort mechanism. Foundation for interval and custom-order problems.

a.sort(key=lambda x: x[1])

See all drills in Sorting →