Introduction

Insertion sort and selection sort are both simple in-place comparison sorts, so they are often introduced in the same chapter of an algorithms course. They share the same quadratic worst-case complexity, but they optimize for different things: insertion sort adapts well to nearly sorted data, while selection sort performs a predictable number of comparisons and relatively few swaps.

How Insertion Sort Works

Insertion sort builds a sorted prefix one element at a time. Each new value is shifted left until it reaches the correct position among the already-sorted elements.

1def insertion_sort(arr):
2    a = arr[:]
3    for i in range(1, len(a)):
4        key = a[i]
5        j = i - 1
6        while j >= 0 and a[j] > key:
7            a[j + 1] = a[j]
8            j -= 1
9        a[j + 1] = key
10    return a
11
12print(insertion_sort([5, 2, 9, 1, 5, 6]))

Because the algorithm only shifts elements as needed, it can be quite fast on partially sorted input.

How Selection Sort Works

Selection sort repeatedly scans the unsorted suffix, finds the minimum element, and swaps it into the next output position.

1def selection_sort(arr):
2    a = arr[:]
3    n = len(a)
4    for i in range(n):
5        min_idx = i
6        for j in range(i + 1, n):
7            if a[j] < a[min_idx]:
8                min_idx = j
9        if min_idx != i:
10            a[i], a[min_idx] = a[min_idx], a[i]
11    return a
12
13print(selection_sort([5, 2, 9, 1, 5, 6]))

Unlike insertion sort, selection sort does not care much whether the input is already nearly sorted. It still scans the unsorted portion fully on each pass.

Compare Their Real Strengths

Both algorithms have:

• 'O(n^2) average and worst-case time complexity'
• 'O(1) extra space usage'
• easy in-place implementations

But their practical behavior differs.

Insertion sort is adaptive. If the list is already close to sorted, it performs much better than the worst case suggests. Selection sort is not adaptive in the same way, because it still performs its full minimum-search pass each time.

Swaps, Stability, and Tradeoffs

Selection sort usually performs fewer swaps than insertion sort, which can matter in environments where writes are expensive. That is its main practical advantage.

Insertion sort, on the other hand, is typically stable in standard implementations, meaning equal elements keep their original order. Selection sort is usually not stable, because swapping the selected minimum into place can reorder equal values.

So if stability matters, insertion sort is usually the safer option. If minimizing writes matters more than preserving order, selection sort may have an argument.

Where Each One Makes Sense

Insertion sort is a better fit when:

• the input is nearly sorted
• stability matters
• the algorithm is being used as a small-sort helper inside a hybrid strategy

Selection sort is a better fit when:

• minimizing swap count matters more than adaptation
• the main goal is educational clarity around repeated minimum selection

In production code, both are mostly limited to small inputs or teaching scenarios.

Why Big-O Alone Is Not Enough

People often stop at the line that both are O(n^2). That misses the more interesting engineering differences. An algorithm can have the same worst-case growth rate and still be noticeably better or worse depending on input order, number of writes, and stability requirements.

That is why insertion sort often appears in practical hybrid algorithms, while selection sort appears more often in explanations than in deployed code.

Common Pitfalls

• Treating insertion sort and selection sort as interchangeable because they share the same asymptotic complexity.
• Choosing selection sort for nearly sorted data, where insertion sort is usually better.
• Forgetting that selection sort is commonly unstable.
• Ignoring swap count when that is the metric that actually matters in a constrained environment.
• Using either algorithm on inputs large enough that a built-in O(n log n) sort is the sensible choice.

Summary

• Insertion sort and selection sort are both in-place quadratic comparison sorts.
• Insertion sort adapts well to nearly sorted input and is usually stable.
• Selection sort performs a predictable number of comparisons and fewer swaps.
• Stability and input order are the most important practical differences.
• For large collections, both are usually replaced by modern O(n log n) algorithms.