Selection Sort Algorithm: Implementation, Complexity O(n²), and Unstable Sort (2026)
Selection Sort is an intuitive in-place comparison sorting algorithm. It divides the input list into two parts: a sorted sublist built from left to right and an unsorted sublist containing the remaining elements. The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion and swaps it with the first unsorted element.
This tutorial covers the algorithm mechanics, step-by-step example, complexity analysis, and the reasons Selection Sort is classified as an unstable sort.
Algorithm and Complexity
The algorithm runs an outer loop from i = 0 to n-2. For each i, find the minimum element in the range [i, n-1] by scanning the unsorted portion. Swap the minimum with the element at index i. Repeat until the entire array is sorted.
Time complexity is O(n²) in all cases (best, average, worst) — the inner loop always scans n-i-1 elements regardless of the data. Space complexity is O(1). The algorithm makes exactly n-1 swaps, which can be fewer than Bubble Sort but more than Insertion Sort.
// C++
void selectionSort(int arr[], int n) {
for(int i=0; iStability Analysis and Comparison
Selection Sort is unstable. When swapping the minimum element to position i, if there are duplicate elements, their relative order may be disturbed. For example, in [4a, 5, 4b, 1], the first pass swaps 1 with 4a, moving 4a past 4b and changing their relative order.
Compared to Bubble Sort, Selection Sort performs fewer swaps (n-1 vs O(n²)) but makes the same number of comparisons. It is not adaptive — performance does not improve on sorted data. Insertion Sort is generally preferred for small or partially sorted datasets.
// C++ — demonstration of instability
struct Item { int key; char id; };
// Sorting [{4,'a'}, {5,'b'}, {4,'c'}, {1,'d'}]
// After first pass: [{1,'d'}, {5,'b'}, {4,'c'}, {4,'a'}]
// Note: 4,'c' now comes before 4,'a' (order of equal keys changed)
// Java — similar with Comparator
// Python — unstable for duplicates
arr = [(4,"a"), (5,"b"), (4,"c"), (1,"d")]
selection_sort(arr)
# [(1,"d"), (4,"c"), (4,"a"), (5,"b")]Frequently Asked Questions
Why is Selection Sort considered unstable?
When the minimum element is swapped into position, it can jump over equal elements, changing their relative order. This makes it unstable.
What is the best use case for Selection Sort?
Selection Sort is useful when memory writes are expensive (flash memory, EEPROM) because it makes only O(n) swaps — fewer than any O(n²) comparison sort.
Originally published on Ayodhyyya. Last updated June 1, 2026.