How does selection-sort work, and where does its $O(n^2)$ cost come from?
Everything goes into an unsorted sequence, then each round scans the whole remainder for its smallest element — the removals cost $n + (n-1) + \dots + 1$, which is quadratic.
* The scan shortens by one each round, and those scan lengths are the triangular sum. *
Selection-sort runs in two phases:
- Insert phase — put all $n$ elements into an unsorted sequence. Each insertion is $O(1)$, so the phase is $O(n)$. No ordering work is done here at all.
- Remove phase — $n$ times, search the entire remaining sequence for the smallest element and take it out. That search costs $n$, then $n-1$, then $n-2$ … as the sequence shrinks.
$$n + (n-1) + \dots + 2 + 1 = \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \Rightarrow O(n^2)$$
Total: $O(n) + O(n^2) = O(n^2)$ — the quadratic phase swallows the linear one.
Worked on the input $(7,4,8,2,5,3,9)$, phase 2 emits the minimum each round and the output grows in sorted order: $(2)$, then $(2,3)$, $(2,3,4)$, $(2,3,4,5)$, $(2,3,4,5,7)$, $(2,3,4,5,7,8)$, $(2,3,4,5,7,8,9)$.
The structural insight: the name says where the work is — the selection of the minimum. Putting data in is trivial; getting it out in order is where the price is paid. And it points straight at the priority queue: give the "find the minimum" step a structure that does it in $O(\log n)$ instead of $O(n)$, and the same two-phase skeleton becomes an $O(n \log n)$ sort (heap-sort).
Go deeper:
Selection sort — the same analysis, plus why heapsort is “selection sort with the right data structure”.
15 Sorting Algorithms in 6 Minutes — Timo Bingmann’s classic visualisation — you can see the quadratic ones crawl.