Selection Sort vs Insertion Sort — Which Should You Use?
Selection Sort and Insertion Sort look like the same algorithm filmed from different angles: both grow a sorted region from the left, one element per step, in place, with simple loops. The resemblance is superficial. The two make opposite trades with the same quadratic budget — Selection Sort spends comparisons lavishly to make almost no writes, while Insertion Sort spends writes freely to skip every comparison it can.
Watch one step of each and the difference is plain. Selection Sort scans the *entire* unsorted region to find its minimum, then makes exactly one swap — no scan can ever be cut short, because the minimum might be anywhere. Insertion Sort takes the *next* element and walks back through the sorted prefix only until it finds the insertion point — on friendly data that walk ends almost immediately, but every step of it shifts an element. One algorithm has a fixed comparison bill and a tiny write bill; the other has a variable bill for both, and presorted input drives it toward zero. To see those opposite rhythms on identical input, race them side by side.
// quick answer
Insertion Sort is the right default of the two, and it is not close. It matches Selection Sort's simplicity and in-place operation while adding the three properties that matter in practice: stability, adaptivity to existing order, and online operation. Real-world data is very often partially sorted — appended logs, mostly-ordered lists with a few edits — and Insertion Sort turns that structure into near-linear running time while Selection Sort obliviously performs its full quadratic scan every single time.
Complexity at a Glance
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
Head-to-Head Differences
| Dimension | Selection Sort | Insertion Sort |
|---|---|---|
| Writes to the array | At most n−1 swaps — close to the minimum possible number of moves | One shift per inversion — heavily scrambled input means quadratically many writes |
| Comparisons | Always n(n−1)/2, because every scan must check the whole remaining region | Only as many as needed to find each insertion point — near n on almost-sorted input |
| Adaptivity to sorted input | None — a sorted array costs exactly as much as a reversed one | Fully adaptive: total cost is O(n + inversions), so presortedness translates directly into speed |
| Stability | Not stable — the placement swap can carry an element past an equal value | Stable — elements shift right only past strictly greater values, so ties keep their order |
| Runtime predictability | Metronomic: identical comparison schedule on every input of a given size | Input-dependent — anywhere between linear and quadratic depending on disorder |
| Online sorting | Impossible — finding the global minimum requires seeing the whole array first | Natural — it maintains a sorted prefix, so new elements can be inserted as they arrive |
| Real-world usage | A niche on write-limited hardware (flash, EEPROM); otherwise pedagogical | The small-array workhorse inside Timsort and introsort — it runs in production constantly |
When to Use Selection Sort
- Every write costs you something: flash and EEPROM cells have limited write cycles, and Selection Sort makes at most n−1 swaps.
- Records are bulky but keys are cheap — when moving an element dwarfs the cost of comparing two, minimizing moves wins.
- You need fixed, input-independent timing, for example a simple embedded routine that must take the same number of cycles every run.
- You are teaching the selection idea — repeatedly extracting the minimum is the conceptual seed of Heap Sort and priority queues.
When to Use Insertion Sort
- The input is small — for a few dozen elements Insertion Sort is typically the fastest sort there is, which is why hybrid sorts delegate to it.
- The data is nearly sorted, or you merely appended a few items to a sorted array: cost tracks inversions, so cleanup is close to linear.
- You need stability — sorting by a second key without scrambling the order produced by the first.
- Elements arrive over time and you want the collection kept sorted continuously rather than sorted once at the end.
Verdict
Insertion Sort is the right default of the two, and it is not close. It matches Selection Sort's simplicity and in-place operation while adding the three properties that matter in practice: stability, adaptivity to existing order, and online operation. Real-world data is very often partially sorted — appended logs, mostly-ordered lists with a few edits — and Insertion Sort turns that structure into near-linear running time while Selection Sort obliviously performs its full quadratic scan every single time.
Selection Sort keeps one honest, physical advantage: it barely writes. If your array lives in memory where writes are slow, power-hungry, or wear the hardware out — EEPROM in a microcontroller, for instance — then paying the fixed comparison cost to achieve at most n−1 swaps is a sensible engineering trade, and it is essentially the only situation where Selection Sort is the professionally correct choice.
A useful way to remember the split: Selection Sort optimizes for the *worst* thing that can happen to your hardware, Insertion Sort optimizes for the *best* thing that can be true of your data. When neither writes nor presortedness dominates, follow the standard libraries — they embed Insertion Sort, not Selection Sort, inside every hybrid sorting algorithm.
Frequently Asked Questions
Which is faster, Selection Sort or Insertion Sort?
Insertion Sort is usually faster. On random data it makes about half as many comparisons because each scan stops at the insertion point, while Selection Sort always scans the full remaining region. On nearly-sorted data Insertion Sort approaches linear time, whereas Selection Sort costs the same regardless of order. Selection Sort only wins when array writes are far more expensive than comparisons.
Why does Selection Sort minimize writes?
It never moves an element until it knows that element's final position. Each pass is pure reading — scanning the unsorted region for the minimum — followed by exactly one swap. That caps total swaps at n−1, close to the minimum any comparison sort can achieve, which is why it suits write-limited media like flash and EEPROM where every write shortens hardware life.
Why is Insertion Sort used in real libraries but Selection Sort is not?
Hybrid sorts like Timsort and introsort need a finisher for small subarrays, and Insertion Sort fits perfectly: it is stable, has a tight cache-friendly inner loop, and is adaptive, so the mostly-ordered fragments produced mid-sort cost almost nothing. Selection Sort offers none of those advantages there — it is slower on average, never adaptive, and not stable.
Is Insertion Sort stable and Selection Sort not?
Yes. Insertion Sort shifts elements only while they are strictly greater than the one being placed, so equal elements keep their original order. Selection Sort swaps the found minimum with the element at the sorted boundary, and that displaced element can jump over an equal value elsewhere in the array, breaking stability. Stable variants of Selection Sort exist but require insertions rather than swaps, forfeiting its low write count.