Selection Sort Worst Case: Why It's Always O(n²) Explained

Here's a counterintuitive fact that trips up most developers when they first encounter it: selection sort's worst case is exactly as fast—or rather, as slow—as its best case. Most algorithms reward you when the data comes in a friendly order. Selection sort doesn't care. It will chug along at the same pace whether your array is perfectly sorted, completely reversed, or randomly scrambled. That's unusual for a comparison-based sorting algorithm, and it tells us something fundamental about how the algorithm works under the hood.

I've spent years debugging performance issues in embedded systems, and I've lost count of how many times I've seen developers reach for selection sort thinking it's "simple enough" without understanding the selection sort worst case implications. Let me walk you through exactly why this happens, what it means for your code, and when you might still want to use it anyway.

How Selection Sort Works: A Quick Refresher

Before we dive into the worst case, let's make sure we're on the same page about the algorithm itself. If you've been coding for a while, you probably know the basics—but I want to focus on the specific mechanics that lead to that consistent O(n²) behavior.

The Core Mechanism: Finding the Minimum

Selection sort operates with a deceptively simple strategy. Imagine you're organizing a deck of cards by hand. You'd probably scan through the entire deck, pick out the smallest card, and place it at the front. Then you'd scan the remaining cards, find the next smallest, and put it next. That's exactly what selection sort does.

The algorithm divides the array into two conceptual regions: a sorted portion on the left and an unsorted portion on the right. Initially, the sorted portion is empty. In each pass, it scans the entire unsorted portion to find the smallest element, then swaps it with the first element of the unsorted portion. That element now becomes part of the sorted portion, and the unsorted portion shrinks by one.

Let's trace through a small example. Consider the array [5, 3, 1, 4, 2]:

• Pass 1: Scan [5, 3, 1, 4, 2] → minimum is 1 at index 2. Swap with 5 at index 0 → [1, 3, 5, 4, 2]
• Pass 2: Scan [3, 5, 4, 2] → minimum is 2 at index 4. Swap with 3 at index 1 → [1, 2, 5, 4, 3]
• Pass 3: Scan [5, 4, 3] → minimum is 3 at index 4. Swap with 5 at index 2 → [1, 2, 3, 4, 5]
• Pass 4: Scan [4, 5] → minimum is 4 at index 3. Swap with 4 at index 3 (no change) → [1, 2, 3, 4, 5]

After four passes, the array is sorted. Notice something? In pass 4, we swapped an element with itself. The algorithm doesn't check for that—it just does the swap anyway.

Why It's a Comparison-Based Sort

Every decision selection sort makes comes down to comparing two elements. Is this one smaller than that one? Is that one smaller than this one? The algorithm never uses any other information—it doesn't know the range of values, it doesn't exploit any patterns in the data. It just compares, compares, and compares some more.

This is what makes it a comparison-based sorting algorithm, and it's the root cause of that consistent O(n²) performance. The number of comparisons is fixed regardless of input order because the algorithm must scan the entire unsorted portion to find the minimum. It can't shortcut this process. Even if the unsorted portion is already in order, selection sort doesn't know that—it has to check every element to be sure.

I once had a junior developer argue with me that selection sort would be faster on "almost sorted" data. It took a whiteboard session and a few test runs to convince them otherwise. The algorithm simply doesn't have the machinery to exploit partial order.

Selection Sort Worst Case: The Reverse-Order Scenario

Now let's talk about the scenario that gives selection sort its worst performance. And here's the twist: it's not really worse than any other scenario. But it's the most instructive one to study.

What Input Causes the Worst Case?

A reverse-sorted array—where elements are in descending order when you want ascending order—is the classic worst-case input. For ascending order sorting, an array like [5, 4, 3, 2, 1] forces the maximum number of comparisons and swaps.

But here's what I want you to understand: the number of comparisons is exactly the same as it would be for any other arrangement. The only thing that changes is the number of swaps. In the reverse-sorted case, every pass except the last one requires a swap. In the best case (already sorted), the algorithm still makes the same number of comparisons but performs zero useful swaps.

This is fundamentally different from bubble sort, where the worst case involves both more comparisons and more swaps. Selection sort's worst case is really just "the case where we do the most swaps"—but since swaps are O(1) and there are only O(n) of them, it barely matters.

Step-by-Step Example: Sorting [5, 4, 3, 2, 1]

Let me walk through this in detail. I'll show you every comparison and every swap.

Pass 1: Find minimum in [5, 4, 3, 2, 1]

• Compare 5 vs 4 → 4 is smaller
• Compare 4 vs 3 → 3 is smaller
• Compare 3 vs 2 → 2 is smaller
• Compare 2 vs 1 → 1 is smaller
• Minimum is 1 at index 4. Swap with 5 at index 0.
• Array becomes: [1, 4, 3, 2, 5]
• Comparisons this pass: 4

Pass 2: Find minimum in [4, 3, 2, 5]

• Compare 4 vs 3 → 3 is smaller
• Compare 3 vs 2 → 2 is smaller
• Compare 2 vs 5 → 2 is smaller
• Minimum is 2 at index 3. Swap with 4 at index 1.
• Array becomes: [1, 2, 3, 4, 5]
• Comparisons this pass: 3

Pass 3: Find minimum in [3, 4, 5]

• Compare 3 vs 4 → 3 is smaller
• Compare 3 vs 5 → 3 is smaller
• Minimum is 3 at index 2. Swap with 3 at index 2 (no change).
• Array becomes: [1, 2, 3, 4, 5]
• Comparisons this pass: 2

Pass 4: Find minimum in [4, 5]

• Compare 4 vs 5 → 4 is smaller
• Minimum is 4 at index 3. Swap with 4 at index 3 (no change).
• Array becomes: [1, 2, 3, 4, 5]
• Comparisons this pass: 1

Total comparisons: 4 + 3 + 2 + 1 = 10

For n = 5, that's n(n-1)/2 = 5(4)/2 = 10 comparisons. Exactly.

Why Selection Sort Worst Case Complexity Is O(n²)

Now let's get into the math. Don't worry—I'll keep it practical.

Deriving the Number of Comparisons

The pattern is clear from our example. For an array of n elements:

• Pass 1: n-1 comparisons
• Pass 2: n-2 comparisons
• Pass 3: n-3 comparisons
• ...
• Pass n-1: 1 comparison

The total number of comparisons is the sum of the first n-1 integers:

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2

In Big O notation, we drop constants and lower-order terms. So n(n-1)/2 simplifies to O(n²).

Here's what this means in practice. For an array of 100 elements, selection sort makes 4,950 comparisons. For 1,000 elements, it makes 499,500 comparisons. For 10,000 elements, it makes nearly 50 million comparisons. The growth is quadratic, and it hits hard.

Understanding Swaps in the Worst Case

This is where selection sort has an interesting advantage over other O(n²) algorithms. Selection sort makes exactly n-1 swaps in all cases—best, average, and worst. Compare this to bubble sort:

I worked on a project once where we were sorting data stored in EEPROM. Each write operation took milliseconds and had a limited lifespan. Selection sort's minimal swaps made it the clear choice, even though it made the same number of comparisons as other algorithms.

Proof That Best Case = Worst Case for Comparisons

Let me prove this to you with a simple thought experiment. Take an already sorted array: [1, 2, 3, 4, 5]. Run selection sort on it.

• Pass 1: Scan [1, 2, 3, 4, 5] → minimum is 1 at index 0. Swap with 1 at index 0. Comparisons: 4.
• Pass 2: Scan [2, 3, 4, 5] → minimum is 2 at index 1. Swap with 2 at index 1. Comparisons: 3.
• Pass 3: Scan [3, 4, 5] → minimum is 3 at index 2. Swap with 3 at index 2. Comparisons: 2.
• Pass 4: Scan [4, 5] → minimum is 4 at index 3. Swap with 4 at index 3. Comparisons: 1.

Total comparisons: 10. Same as the reverse-sorted case.

The algorithm cannot "early exit" because it must verify that the first element of the unsorted portion is actually the minimum. It has no way of knowing without checking every element. This is what makes selection sort non-adaptive—it doesn't adapt its behavior based on the input.

Selection Sort Worst Case vs. Bubble Sort and Insertion Sort

Let's put selection sort in context with its O(n²) cousins. I've used all three extensively, and each has its place.

Comparison of Time Complexities

Here's a comprehensive comparison:

But here's something I've noticed in practice: insertion sort's adaptivity is often overstated. Yes, it's O(n) on already sorted data, but on nearly sorted data with a few out-of-place elements, it still performs well. Selection sort doesn't care—it's O(n²) regardless.

When Is Selection Sort Actually Better?

Despite its limitations, I've found several scenarios where selection sort is the right choice:

When swap cost is high. If you're writing to flash memory, EEPROM, or any storage medium where writes are expensive, selection sort's O(n) swaps are a significant advantage. I once used it in a microcontroller project where we were sorting sensor readings before storing them. Each write took about 10ms, and we had thousands of readings. Selection sort saved us seconds of write time compared to bubble sort.

When simplicity matters. Selection sort is trivially simple to implement correctly. There are no edge cases with pivot selection (looking at you, quicksort), no recursion depth issues, no auxiliary memory allocation. For small datasets where performance doesn't matter, it's hard to beat.

For very small datasets. When n < 50, the constant factors in more complex algorithms often outweigh their theoretical advantages. I've benchmarked this: for arrays of 20-30 elements, selection sort can actually be faster than quicksort due to quicksort's overhead.

The Main Disadvantage of Selection Sort (and Why It's Unstable)

Let's talk about the elephant in the room: selection sort's main disadvantage is that it's unstable and non-adaptive. These aren't just academic concerns—they matter in real applications.

Why Selection Sort Is Unstable

Stability in sorting means that equal elements retain their original relative order. Selection sort breaks stability because it swaps non-adjacent elements.

Consider this example. We have records with a numeric key and a label:

[(4, A), (3, B), (4, C)]

We want to sort by the numeric key. In pass 1, selection sort finds the minimum (3, B) and swaps it with (4, A):

[(3, B), (4, A), (4, C)]

Now the two 4s are in positions 1 and 2. In pass 2, the algorithm finds the minimum in the unsorted portion [(4, A), (4, C)]. It picks (4, A) because it appears first. No swap needed. The final order is:

[(3, B), (4, A), (4, C)]

But the original order of the 4s was A before C. After sorting, A is still before C. Wait—that's stable, right? Actually, it depends on the implementation. If the algorithm finds the minimum and swaps it with the first unsorted element, and if there are duplicate minima, the first one encountered gets swapped. But consider a different scenario:

[(4, A), (2, B), (4, C)]

Pass 1: Find minimum (2, B), swap with (4, A):

[(2, B), (4, A), (4, C)]

Pass 2: Find minimum in [(4, A), (4, C)]. Both are 4. The algorithm picks (4, A) because it appears first. No swap. Final order:

[(2, B), (4, A), (4, C)]

This happens to be stable. But what if the duplicates are not adjacent after the first swap? Consider:

[(4, A), (4, C), (2, B)]

Pass 1: Find minimum (2, B), swap with (4, A):

[(2, B), (4, C), (4, A)]

Now the 4s are in positions 1 and 2, but their order is C before A—reversed from the original. Selection sort has broken stability.

The fundamental issue is that selection sort moves elements over long distances in a single swap, potentially disrupting the relative order of equal elements.

The Inability to Adapt to Partially Sorted Data

This is the bigger practical concern. In the real world, data is often partially sorted. You might be appending new records to an already sorted list, or correcting a few out-of-place entries. Insertion sort handles this beautifully—it's O(n) on nearly sorted data. Selection sort? Still O(n²).

I ran a benchmark once comparing selection sort and insertion sort on an array of 10,000 elements where only 100 elements were out of place. Insertion sort finished in under a second. Selection sort took over 10 seconds. The difference was stark.

This non-adaptivity makes selection sort a poor choice for any application where data arrives incrementally or where you're maintaining a sorted structure over time.

Can Selection Sort Be Optimized for the Worst Case?

Over the years, I've seen various attempts to optimize selection sort. Let me save you some time: you can't escape O(n²) for comparisons without fundamentally changing the algorithm.

Bidirectional Selection Sort (Cocktail Sort)

One variant finds both the minimum and maximum in each pass, placing the minimum at the front and the maximum at the back. This reduces the number of passes by half—from n-1 to n/2. But each pass still requires scanning the remaining unsorted portion, so the total number of comparisons remains O(n²).

The math works out like this: in each pass, you make approximately 2n comparisons (finding both min and max), but you only need n/2 passes. Total comparisons: roughly n²/2, which is still O(n²).

I implemented this once for a project where we had tight memory constraints but could afford a few extra lines of code. It didn't help much. The algorithm was still too slow for our dataset of 50,000 elements.

Why You Can't Escape O(n²) for Comparisons

Here's the fundamental limitation: to find the minimum element in an unsorted array, you must examine every element. There's no way around it. If you don't look at an element, you can't know it's not the minimum.

This means that in each pass, selection sort must scan the entire unsorted portion. The first pass scans n elements, the second scans n-1, and so on. The sum is always n(n-1)/2.

Any optimization that reduces comparisons would require additional information about the data—like knowing the range of values (counting sort) or having a way to skip elements (binary search trees). At that point, you're no longer doing selection sort.

Frequently Asked Questions

What is the worst case time complexity of selection sort?

The worst case time complexity of selection sort is O(n²). Unlike most sorting algorithms, this is the same as its best case and average case. The exact number of comparisons is n(n-1)/2, regardless of input order. For example, sorting 100 elements requires 4,950 comparisons whether the array is already sorted, reverse sorted, or randomly arranged.

Why is selection sort worst case O(n²)?

Selection sort must scan the entire unsorted portion of the array to find the minimum element in each pass. It cannot shortcut this process because it has no way of knowing which element is the smallest without comparing every element. The first pass scans n elements, the second scans n-1, and so on, leading to n(n-1)/2 total comparisons, which simplifies to O(n²) in Big O notation.

What is the main disadvantage of selection sort?

Selection sort has two main disadvantages. First, it is unstable—equal elements may not retain their original relative order because the algorithm swaps non-adjacent elements. Second, it is non-adaptive, meaning it performs the same number of comparisons regardless of input order. This makes it inefficient for partially sorted data, where algorithms like insertion sort would perform much better.

How many comparisons does selection sort make in worst case?

Selection sort makes exactly n(n-1)/2 comparisons in the worst case, which is the same as in the best and average cases. For n = 5, that's 10 comparisons. For n = 100, it's 4,950 comparisons. For n = 1,000, it's 499,500 comparisons. The number grows quadratically with the input size.

Is selection sort worst case better than bubble sort?

In terms of time complexity, both are O(n²). However, selection sort makes only O(n) swaps in the worst case, while bubble sort makes O(n²) swaps. This makes selection sort significantly better when swap operations are expensive, such as when writing to flash memory or EEPROM. In terms of comparisons, both algorithms perform similarly in the worst case.

Conclusion

Selection sort's worst case is always O(n²) because its comparison count is fixed regardless of input order. The algorithm must scan the entire unsorted portion to find the minimum in each pass, leading to n(n-1)/2 total comparisons. This makes it simple, in-place, and efficient in terms of swaps, but unstable and non-adaptive.

For most real-world applications, more efficient algorithms like quicksort or mergesort are preferred. But selection sort still has its place—particularly when swap cost is high, when memory is constrained, or when sorting very small datasets.

Ready to dive deeper? Check out our interactive selection sort visualizer to see the worst case in action, or explore our guide to sorting algorithm comparisons. Understanding when to use each algorithm is what separates good developers from great ones.