Insertion & Selection Sort

DSA · Beginner

Definition

Insertion sort inserts each element into its place in the sorted left part; selection sort repeatedly picks the minimum.

Simple sorts that teach loop invariants and work well on tiny or nearly sorted inputs.

Diagram

Flowchart

Example: Insertion sort

a = [4, 3, 1, 2]
for i in range(1, len(a)):
    k, j = a[i], i - 1
    while j >= 0 and a[j] > k:
        a[j + 1] = a[j]; j -= 1
    a[j + 1] = k
print(a)

Output: [1, 2, 3, 4]

Complexity

O(n²) worst · insertion O(n) on sorted input · O(1) space

Key points

Insertion sort is stable
Selection sort makes at most n swaps

Interview questions

Best case of insertion sort?

O(n) when the array is already sorted.