Selection Sort vs Quick Sort — Which Should You Use?
On paper these two share more than most pairs on this site: both are unstable, both sort essentially in place, and both work by repeatedly putting elements into position rather than merging sorted pieces. From there they diverge completely. Quick Sort is the fastest general-purpose comparison sort in practice — average O(n log n) with excellent constants and cache behavior. Selection Sort is quadratic, always, with no lucky inputs and no clever escape.
But 'always' cuts both ways, and that is the interesting part of this matchup. Quick Sort's speed is an average: an unlucky pivot sequence degrades it to O(n²) with recursion depth to match, which is why production versions carry defenses — randomized or median-of-three pivots, and introsort's switch to heapsort past a depth limit. Selection Sort has no variance to defend against. Exactly n(n−1)/2 comparisons and at most n−1 swaps, for every possible input, with two nested loops and not a byte of stack growth.
That profile — dead predictable, recursion-free, tiny code, minimal writes — is worth something in one specific world: very small arrays on very constrained hardware. Everywhere else, the average case rules and Quick Sort's dominance is total. Race them side by side and the gap is obvious well before the array gets large.
// quick answer
For anything resembling normal workloads, Quick Sort wins overwhelmingly. Average-case O(n log n) against unconditional Θ(n²) is not a contest once n clears a few dozen; at 10,000 elements Selection Sort does about 50 million comparisons where Quick Sort averages around 130,000. Neither is stable, so stability cannot rescue Selection Sort in this pairing the way it does elsewhere.
Complexity at a Glance
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
Head-to-Head Differences
| Dimension | Selection Sort | Quick Sort |
|---|---|---|
| Predictability | Perfectly deterministic cost: the same n does exactly the same work on any input | Input-dependent: fast on average, but pathological pivot sequences hit O(n²) unless the implementation guards against them |
| Stability | Unstable — the placement swap can jump an element over an equal one | Unstable — partitioning freely reorders equal keys |
| Swaps and writes | At most n−1 swaps — the fewest writes of the classic sorts | On the order of n log n swaps on average, though each can move an element a long distance |
| Recursion vs iteration | Two nested loops; O(1) control state, zero stack risk | Recursive: O(log n) stack on average, O(n) in the unguarded worst case — a real concern on tiny embedded stacks |
| Adaptivity to sorted input | None — sorted input costs the full quadratic comparison count | None in the classic form; worse, sorted input is the textbook worst case for a naive first-element pivot |
| Implementation complexity | Trivial to write correctly and to verify by inspection | Easy to write badly: pivot strategy, partition edge cases, duplicate-heavy inputs, and depth safety all need care |
| Real-world usage | Teaching, and small fixed-size tables in firmware where writes or stack are scarce | The engine of introsort/std::sort and many runtime libraries — the default in-place sort of the industry |
When to Use Selection Sort
- A microcontroller with a tiny stack: no recursion, no allocation, no worst-case depth to budget for.
- The input is a small, fixed-size table (tens of elements) sorted rarely — simplicity beats asymptotics here.
- Memory writes are costly (flash/EEPROM wear): at most n−1 swaps is a hard guarantee.
- You need constant, auditable timing for a simple control loop — the same n always takes the same work.
- Code footprint matters: it compiles to a handful of instructions and is verifiable at a glance.
When to Use Quick Sort
- Any general-purpose sorting of more than a few dozen elements — average O(n log n) with the best constants in class.
- You want in-place speed at scale without a merge buffer.
- You control the implementation and can add the standard defenses (randomized pivot, introsort depth limit).
- Cache performance matters: the partition step streams contiguous memory beautifully.
Verdict
For anything resembling normal workloads, Quick Sort wins overwhelmingly. Average-case O(n log n) against unconditional Θ(n²) is not a contest once n clears a few dozen; at 10,000 elements Selection Sort does about 50 million comparisons where Quick Sort averages around 130,000. Neither is stable, so stability cannot rescue Selection Sort in this pairing the way it does elsewhere.
Selection Sort's case rests entirely on the words *always* and *nothing*: always the same cost, nothing on the stack, nothing allocated, nothing surprising. On an 8-bit microcontroller sorting a 20-entry sensor table inside an interrupt budget, those words matter more than asymptotic elegance — and honestly, at n=20 the asymptotic gap barely exists. That is the one arena where choosing it is engineering rather than nostalgia.
So: Quick Sort (hardened, or via your standard library) for real data; Selection Sort when the machine is tiny, the array is tinier, and predictability is the spec. To calibrate your intuition for where "tiny" ends, race them side by side and grow the array until the quadratic curve becomes unmistakable.
Frequently Asked Questions
Are Selection Sort and Quick Sort both unstable?
Yes. Selection Sort swaps the found minimum across the array, which can carry it past an equal element. Quick Sort partitions by swapping elements across long distances with no regard for the order of equal keys. If you need stability, neither qualifies in its standard in-place form — use Merge Sort or Insertion Sort instead.
Can Quick Sort really degrade to O(n²)?
Yes, when pivots repeatedly split the array badly — classically, a first-element pivot on already-sorted input produces n levels of n-scale partitions and deep recursion. Production implementations prevent this with randomized or median-of-three pivot selection, and introsort adds a hard depth limit that falls back to heapsort, capping the worst case at O(n log n).
Why would anyone pick Selection Sort on embedded hardware?
Because it offers guarantees Quick Sort cannot: no recursion or stack growth, no allocation, at most n−1 writes, and identical work for every input of the same size, making worst-case execution time trivial to bound. For a small fixed table on a microcontroller — especially in wear-limited flash or under a strict interrupt budget — those properties outweigh raw speed.
At what size does Quick Sort clearly win?
The comparison-count gap becomes decisive somewhere in the tens of elements; by around 50 to 100 elements Quick Sort is unambiguously faster on ordinary hardware, and the ratio keeps widening — quadratic versus n log n. Below roughly 16 elements the simple quadratic sorts often win on constants, which is exactly why introsort switches to Insertion Sort there.