What is the time complexity of selection sort?

Best case O(n²). Average case O(n²). Worst case O(n²). Space complexity is O(1). The inner loop has no early exit, so all three cases are Θ(n²).

Selection sort

easy

Always exactly n−1 swaps, whatever the input - which makes it the right choice when writes are far more expensive than reads. The comparison count never changes either, so there is no best case to exploit.

Best O(n²)Average O(n²)Worst O(n²)Space O(1)Not stableIn place

Loading the selection sort engine…

Where to go next

Bubble sort

easy

Repeatedly swap neighbours until nothing moves.

Heap sort

medium

Build a heap in the array, then extract the maximum n times.

Insertion sort

easy

How you sort a hand of cards.