Selection sort is one of the cleanest algorithms to reason about, which is exactly why interviewers still ask about it. Its time complexity does not depend on best or worst case input order, making it a great vehicle for explaining algorithm analysis fundamentals.
What Selection Sort Actually Does
Selection sort repeatedly finds the minimum element from the unsorted region and places it at the beginning of that region.
After the first pass, index 0 is correct. After the second pass, index 1 is correct. This repeats until the array is sorted.
- Pass 1 scans n elements
- Pass 2 scans n-1 elements
- Pass 3 scans n-2 elements
Why Time Complexity is O(n^2)
The total comparisons are (n-1) + (n-2) + ... + 1, which equals n(n-1)/2.
When we drop constants and lower-order terms, Big O becomes O(n^2). This is true for best, average, and worst case.
Selection sort does the same number of comparisons even if the array is already sorted.
Where Selection Sort Can Still Be Useful
In modern production systems, we rarely choose selection sort for large datasets. But there are scenarios where fewer swaps are useful.
If swap operations are expensive relative to comparisons, selection sort can outperform some alternatives despite similar asymptotic complexity.
- Small arrays
- Memory-constrained systems
- Teaching and interview communication
How to Explain it in an Interview
Start with intuition, then derive complexity from number of passes and work per pass. End with tradeoffs and practical alternatives.
A concise, structured explanation often scores better than jumping directly to formulas.
