Selection Sort — 3-Second Freeze with 50,000 Elements

Sorting is one of the most fundamental operations in computing. Every time you see a leaderboard ranked by score, a product list sorted by price, or a contact list arranged alphabetically, a sorting algorithm made that happen. Understanding sorting algorithms is not just academic — it's the foundation that explains why some apps feel instant while others crawl, and it's one of the first things technical interviewers probe to see how you think about problems.

Selection sort solves the classic problem of arranging an unsorted list into order. It does it in the most intuitive way possible: scan the list, find the smallest item, move it to the front, then repeat on the shrinking remainder. It's not the fastest algorithm in the world — we'll be honest about that — but it's the perfect algorithm to learn first because its logic is transparent. There are no tricks, no recursion, no magic. Every step does exactly what it looks like.

By the end of this article you'll be able to trace selection sort by hand on any array, write a fully working implementation in Java from memory, explain its time and space complexity to an interviewer, and know exactly when it's a reasonable choice versus when you should reach for something better. Let's build this up from the ground floor.

Selection Sort: The Quadratic Algorithm That Still Teaches a Core Lesson

Selection sort is a comparison-based sorting algorithm that repeatedly finds the minimum element from the unsorted portion and swaps it into the sorted position. It operates in O(n²) time regardless of input order — no early exit, no adaptivity. For 50,000 elements, that means roughly 1.25 billion comparisons, which on modern hardware translates to a 2–3 second freeze. The algorithm divides the array into a sorted prefix and an unsorted suffix, growing the sorted region by one element per pass. It performs exactly n-1 swaps in the worst case, making it write-efficient but read-heavy. In practice, selection sort is never used for general-purpose sorting. Its only niche is when writes are astronomically expensive — think EEPROM or flash memory with limited write cycles — and you need to minimize swaps. Even then, it's rarely the right choice. The real value of selection sort is pedagogical: it's the simplest algorithm that demonstrates the concept of in-place sorting and the cost of naive O(n²) behavior. Understanding why it's slow — the lack of early termination, the fixed number of comparisons — builds intuition for why better algorithms like quicksort or heapsort exist.

How Selection Sort Actually Works — The Step-by-Step Logic

Let's use a concrete example before we touch any code. Say you have this array of five numbers:

[64, 25, 12, 22, 11]

Here's what selection sort does on every pass:

Pass 1: Scan the entire array. The smallest value is 11 (at index 4). Swap it with the element at index 0 (which is 64). Array becomes: [11, 25, 12, 22, 64]. The first position is now locked — it's sorted.

Pass 2: Scan from index 1 onwards. The smallest value is 12 (at index 2). Swap it with index 1 (which is 25). Array becomes: [11, 12, 25, 22, 64]. First two positions locked.

Pass 3: Scan from index 2 onwards. Smallest is 22 (at index 3). Swap with index 2. Array: [11, 12, 22, 25, 64].

Pass 4: Scan from index 3. Smallest is 25, already in position. No swap needed.

Notice the pattern: after every pass, the sorted region on the left grows by exactly one element. The algorithm never goes back and revisits the sorted section. That boundary between 'sorted' and 'unsorted' is the heart of selection sort.

public class SelectionSortTrace {

    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};

        System.out.println("=== Selection Sort — Trace Mode ===");
        System.out.print("Original array: ");
        printArray(numbers);
        System.out.println();

        int arrayLength = numbers.length;

        // Outer loop: moves the 'sorted boundary' forward one step each pass
        for (int sortedBoundary = 0; sortedBoundary < arrayLength - 1; sortedBoundary++) {

            // Assume the first element in the unsorted region is the minimum
            int minIndex = sortedBoundary;

            // Inner loop: scan the entire unsorted region to find the true minimum
            for (int scanner = sortedBoundary + 1; scanner < arrayLength; scanner++) {
                if (numbers[scanner] < numbers[minIndex]) {
                    minIndex = scanner; // Found a new minimum — update the index
                }
            }

            // Only swap if the minimum isn't already in the correct position
            if (minIndex != sortedBoundary) {
                int temp = numbers[sortedBoundary];       // Save the value being displaced
                numbers[sortedBoundary] = numbers[minIndex]; // Move minimum to sorted boundary
                numbers[minIndex] = temp;                 // Put displaced value where minimum was
            }

            // Print the array after each pass so we can watch the sort happen
            System.out.print("After pass " + (sortedBoundary + 1) + ":       ");
            printArray(numbers);
            System.out.println("  (positions 0-" + sortedBoundary + " sorted)");
        }

        System.out.println();
        System.out.print("Final sorted array: ");
        printArray(numbers);
    }

    // Helper method to print an array in a readable format
    static void printArray(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) System.out.print(", ");
        }
        System.out.print("]");
    }
}

Selection Sort Implementations in Python and C++

Selection sort is straightforward to implement in any language. Below are idiomatic implementations in Python and C++ that mirror the Java version. Both follow the same O(n²) comparison count and O(1) space complexity.

Python ```python def selection_sort(arr): n = len(arr) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j if min_idx != i: arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr

# Example usage arr = [64, 25, 12, 22, 11] print(selection_sort(arr)) # Output: [11, 12, 22, 25, 64] ```

C++ ```cpp #include <iostream> #include <vector>

void selectionSort(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { int minIdx = i; for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[minIdx]) { minIdx = j; } } if (minIdx != i) { std::swap(arr[i], arr[minIdx]); } } }

int main() { std::vector<int> arr = {64, 25, 12, 22, 11}; selectionSort(arr); for (int x : arr) std::cout << x << " "; // Output: 11 12 22 25 64 return 0; } ```

Visual Walkthrough: Tracking the Minimum Across Passes

Let's trace selection sort on the array [64, 25, 12, 22, 11] with a focus on how the minimum index is updated during each pass. The table below shows the state of the sorted and unsorted regions after each pass, and the progress of scanning the minimum.

Notice that in each pass, the minimum is found by scanning the entire unsorted region. The sorted region grows by one element per pass, and the algorithm never revisits it.

Visual Walkthrough: Text-Based Table of Minimum Tracking Across Passes

Here is a compact text-based table that tracks the minimum value and its index during each pass of selection sort on the array [64, 25, 12, 22, 11]. The table shows the initial assumption, each comparison that updates the minimum, and final swap (or no-op).

This fine-grained view shows exactly when the minimum candidate changes and why. It's useful for debugging or teaching the inner workings.

Time and Space Complexity — Why Selection Sort Is Slow (And When That's OK)

Every time you hear someone say an algorithm is 'fast' or 'slow', they're talking about complexity — how the algorithm's workload grows as the input grows. This is measured in Big O notation.

Time Complexity — O(n²)

For an array of n elements, the outer loop runs n-1 times. On the first pass the inner loop does n-1 comparisons, on the second pass n-2, on the third n-3, and so on. Add those up:

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

In Big O terms, we drop the constant and lower-order terms: that's O(n²). Double the input size, and the work roughly quadruples. That's why selection sort gets painful on large datasets.

Critically, selection sort always does O(n²) comparisons — even if the array is already sorted. It has no way to detect that early. This is different from insertion sort, which can exit early on a nearly-sorted list.

Space Complexity — O(1)

Selection sort sorts in-place. It only ever uses one extra variable (temp) for the swap, regardless of how large the array is. That's O(1) — constant extra space. This is actually selection sort's secret strength: it's memory-efficient in environments where RAM is precious.

public class ComplexityDemo {

    public static void main(String[] args) {
        // Demonstrates that comparison count matches n*(n-1)/2 exactly
        int[] testSizes = {5, 10, 20, 50};

        System.out.println("=== Selection Sort Comparison Count vs n*(n-1)/2 ===");
        System.out.printf("%-12s %-20s %-20s%n", "Array Size", "Actual Comparisons", "Formula n*(n-1)/2");
        System.out.println("-".repeat(55));

        for (int size : testSizes) {
            // Build a worst-case (reverse-sorted) array of this size
            int[] reverseArray = new int[size];
            for (int i = 0; i < size; i++) {
                reverseArray[i] = size - i; // [5,4,3,2,1] for size 5
            }

            long comparisonCount = countComparisons(reverseArray);
            long formulaResult = (long) size * (size - 1) / 2;

            System.out.printf("%-12d %-20d %-20d%n", size, comparisonCount, formulaResult);
        }

        System.out.println();
        System.out.println("Key insight: comparisons match EXACTLY — selection sort");
        System.out.println("always does n*(n-1)/2 comparisons, no matter the input order.");
    }

    // Runs selection sort and counts every comparison made
    static long countComparisons(int[] array) {
        int[] copy = array.clone(); // Work on a copy so we don't modify the original
        long comparisons = 0;
        int length = copy.length;

        for (int sortedBoundary = 0; sortedBoundary < length - 1; sortedBoundary++) {
            int minIndex = sortedBoundary;
            for (int scanner = sortedBoundary + 1; scanner < length; scanner++) {
                comparisons++; // Count every time we compare two elements
                if (copy[scanner] < copy[minIndex]) {
                    minIndex = scanner;
                }
            }
            // Perform the swap
            int temp = copy[sortedBoundary];
            copy[sortedBoundary] = copy[minIndex];
            copy[minIndex] = temp;
        }
        return comparisons;
    }
}

Gotchas — The Mistakes Almost Every Beginner Makes

Writing selection sort from scratch in an interview is a classic test. Most candidates understand the concept but trip over two or three implementation details that silently corrupt the result. Here are the real ones.

Mistake 1 — Off-by-one in the outer loop boundary

Students often write sortedBoundary < arrayLength instead of sortedBoundary < arrayLength - 1. When there's only one element left in the unsorted region, it's already in the right place — there's nothing to compare it against. The extra iteration wastes a cycle and can cause an ArrayIndexOutOfBoundsException in the inner loop.

Mistake 2 — Unconditional swapping

A very common version skips the if (minIndex != sortedBoundary) check and always performs the swap. The result is still correct, but you're doing unnecessary work every time the minimum is already in position. More importantly, this breaks stability: you might swap an element with itself unnecessarily in an extended version of the algorithm.

Mistake 3 — Sorting the original instead of a copy

In real code, callers are often surprised when their original array is modified. Java arrays are passed by reference, not by value. If a method receives an array, sorts it using selection sort, and the caller still needs the original order, you've silently corrupted their data. Always clarify whether to sort in-place or return a new sorted array.

public class GotchasFixed {

    public static void main(String[] args) {
        int[] original = {29, 10, 14, 37, 13};

        System.out.println("=== Demonstrating All Three Gotchas ===");
        System.out.print("Original array before sorting: ");
        printArray(original);

        // GOTCHA 3 FIX: Sort a clone so the original is preserved
        int[] sorted = selectionSort(original.clone());

        System.out.print("\nOriginal array after sorting:  ");
        printArray(original); // Should be unchanged
        System.out.print("\nSorted copy:                   ");
        printArray(sorted);
    }

    static int[] selectionSort(int[] array) {
        int length = array.length;

        // GOTCHA 1 FIX: outer loop goes to length-1, not length
        // When one element remains in the unsorted region, it's already in place
        for (int sortedBoundary = 0; sortedBoundary < length - 1; sortedBoundary++) {
            int minIndex = sortedBoundary;

            for (int scanner = sortedBoundary + 1; scanner < length; scanner++) {
                if (array[scanner] < array[minIndex]) {
                    minIndex = scanner;
                }
            }

            // GOTCHA 2 FIX: only swap when the minimum is NOT already in position
            // This avoids a pointless write operation and preserves relative order
            // in cases where the same value appears more than once
            if (minIndex != sortedBoundary) {
                int displaced = array[sortedBoundary];
                array[sortedBoundary] = array[minIndex];
                array[minIndex] = displaced;
            }
        }
        return array;
    }

    static void printArray(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Stability — Why Selection Sort Is Not Stable and How to Fix It

A stable sorting algorithm preserves the relative order of elements with equal keys. For example, if you sort people by age, and two people are both 30, a stable sort keeps them in the original order. This matters when sorting by multiple keys.

Selection sort is inherently unstable because it swaps non-adjacent elements. Suppose you have two equal values — calling them A and B — where A appears before B in the original array. If the minimum is found later and swapped to an earlier position, B could end up before A, reversing their original order.

Can selection sort be made stable? Yes, but at a cost. Instead of swapping, you could shift elements — like insertion sort — but that adds O(n) writes per pass. The resulting algorithm is no longer the same; it's a hybrid. For most practical purposes, if you need stability, use insertion sort (O(n²)) or merge sort (O(n log n)).

public class StabilityDemo {
    // Demonstrate instability with two equal values
    static class Item {
        int key;
        int originalIndex;
        Item(int key, int idx) { this.key = key; this.originalIndex = idx; }
    }

    public static void main(String[] args) {
        Item[] items = {new Item(3,1), new Item(1,2), new Item(3,3), new Item(2,4)};
        // Sort by key (selection sort)
        for (int i = 0; i < items.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < items.length; j++) {
                if (items[j].key < items[minIdx].key) minIdx = j;
            }
            // Swap
            Item temp = items[i];
            items[i] = items[minIdx];
            items[minIdx] = temp;
        }
        // Print: originalIndex order may not preserve relative order of equal keys
        for (Item it : items) {
            System.out.println("key=" + it.key + " origIdx=" + it.originalIndex);
        }
    }
}

When to Use Selection Sort — Real-World Trade-offs and Alternatives

Selection sort has a narrow sweet spot: when writes are expensive. Flash memory, EEPROM, or any storage where each write degrades the medium benefits from selection sort's minimal swaps (at most n-1). In those contexts, comparisons are cheap but writes are destructive.

Other scenarios: - Small arrays (< 20 elements): Simplicity of selection sort can outweigh performance gains from more complex algorithms. - Teaching tool: Its transparency makes it ideal for introducing sorting. - Embedded systems with tight memory: O(1) space is attractive when RAM is measured in bytes.

When NOT to use it: - Nearly-sorted data: Insertion sort is O(n) vs selection sort's O(n²). - Large datasets: O(n log n) algorithms dominate. - Stability required: Use a stable algorithm.

Here's a quick comparison with other simple sorts.

public class TradeoffDemo {
    // Compare selection sort vs insertion sort on nearly-sorted array
    public static void main(String[] args) {
        int[] nearlySorted = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11, 12};
        int[] copy1 = nearlySorted.clone();
        int[] copy2 = nearlySorted.clone();

        long start = System.nanoTime();
        selectionSort(copy1);
        long selTime = System.nanoTime() - start;

        start = System.nanoTime();
        insertionSort(copy2);
        long insTime = System.nanoTime() - start;

        System.out.println("Selection sort time: " + selTime + " ns");
        System.out.println("Insertion sort time: " + insTime + " ns");
        System.out.println("Insertion sort is " + (selTime / (double) insTime) + "x faster on nearly-sorted data.");
    }

    static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) minIdx = j;
            }
            if (minIdx != i) {
                int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp;
            }
        }
    }

    static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

Advantages and Disadvantages of Selection Sort

Selection sort is rarely the default choice, but it has niche strengths that make it valuable in specific environments. The table below summarises its pros and cons, with special emphasis on the minimum-swaps advantage.

The highlighted advantage — fewest memory writes — is particularly relevant in embedded systems and storage-aware applications.

Advantages and Disadvantages of Selection Sort (Minimum-Swaps Emphasized)

This table focuses specifically on the advantage of having the fewest writes among O(n²) sorts. It is useful when selecting an algorithm for write-limited environments.

When the cost of a write (time or wear) dwarfs the cost of a comparison, selection sort's swap-minimising property becomes the deciding factor. For example, writing to EEPROM can be 1000x slower than a comparison.

Applications of Selection Sort: When Minimal Writes Matter (EEPROM, NOR Flash)

Selection sort's guarantee of at most n-1 swaps makes it uniquely suited for environments where writing to memory is expensive or destructive. Key applications include:

• EEPROM: Each write cycle degrades the memory cell; selection sort minimises writes, extending lifespan. Used for sorting configuration data or calibration tables on microcontrollers.
• NOR Flash: Commonly used in bootloaders and firmware updates. Byte-addressable and slow to write; selection sort reduces wear on these cells.
• SD cards and SSDs: While modern drives have wear-leveling, reducing write operations still helps longevity in data-logging devices.
• Low-power embedded systems: Reducing writes also reduces energy consumption, critical for battery-powered devices.

In all these cases, comparisons are cheap (CPU cycles) but writes are expensive (time, energy, wear). Selection sort trades extra comparisons for the smallest possible number of writes. For datasets under a few hundred elements, this trade-off is often acceptable.

Real-World Applications of Selection Sort (EEPROM, NOR Flash)

Selection sort's minimal-write property is exploited in various real-world systems where memory endurance is a concern. Below are specific use cases:

• Automotive ECU configuration: EEPROM stores lookup tables; sorting calibration data with selection sort reduces wear.
• Smart meters: Logging energy consumption data to flash memory; selection sort preserves flash lifespan.
• Medical implants: Write-limited memory for patient records; selection sort ensures minimal writes during data processing.
• IoT sensors: Transmitting sorted sensor readings; using selection sort on the device reduces flash write cycles, extending device deployment time.

In each case, the key is that the dataset is small (tens to hundreds of elements) and the write operation is several orders of magnitude more expensive than a comparison. Selection sort's predictable behavior also aids in real-time scheduling.

Selection Sort Algorithm — The Barebones Pseudocode That Reveals the Pattern

Most tutorials bury the algorithm under buzzwords. Here's the stripped-down truth: selection sort works by repeatedly finding the minimum element from the unsorted region and swapping it into position. No recursion. No extra memory. Just two nested loops and a swap.

The outer loop runs n-1 times. For each iteration i, the inner loop scans from i+1 to n-1, tracking the index of the smallest value. When the scan completes, swap arr[i] with arr[min_idx]. After n-1 passes, the array is sorted.

This is why selection sort teaches a core lesson: every comparison-based sort must make Ω(n log n) comparisons in the worst case. Selection sort makes exactly n(n-1)/2 comparisons. Always. No early exit, no adaptive behavior. That's both its weakness and why it's easy to analyze.

// io.thecodeforge — dsa tutorial

public class SelectionSortAlgorithm {
    public static void selectionSort(int[] unsorted) {
        int n = unsorted.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (unsorted[j] < unsorted[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap found minimum with first position
            int swapCache = unsorted[minIndex];
            unsorted[minIndex] = unsorted[i];
            unsorted[i] = swapCache;
        }
    }

    public static void main(String[] args) {
        int[] data = {29, 72, 98, 13, 87, 66, 52, 51, 36};
        selectionSort(data);
        System.out.print("Sorted output: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

Disadvantages of Selection Sort — Where It Bleeds Performance

Selection sort's reputation for being slow isn't just theoretical — it's a fact of life on any non-trivial data set. Here's where it falls apart:

Quadratic comparisons regardless. With 100,000 elements, selection sort makes ~5 billion comparisons. Insertion sort can cut that in half if the data is nearly sorted. Selection sort never gets a break.

No stability by default. The natural implementation is unstable. Swap can and will move identical elements relative to each other. If you're sorting objects where tie-breaking order matters, you just broke something. The fix (shifting instead of swapping) doubles the write cost.

Cache-unfriendly scanning. The inner loop sweeps the entire remaining array linearly on every pass. This defeats CPU cache locality patterns that benefit from smaller working sets. For large arrays, you'll have L1 cache misses everywhere.

Identical path regardless of data. Unlike quicksort or Timsort, selection sort offers zero early termination. Even if the array is already sorted, it runs the same O(n²) comparisons. That's a full waste of CPU cycles.

// io.thecodeforge — dsa tutorial

public class SelectionSortDisadvantages {
    public static void main(String[] args) {
        int[] alreadySorted = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int comparisons = 0;
        int n = alreadySorted.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                comparisons++;
                if (alreadySorted[j] < alreadySorted[minIndex]) {
                    minIndex = j;
                }
            }
        }
        System.out.println("Comparisons on sorted data: " + comparisons);
    }
}

Similar Sorting Algorithms — Where Selection Sort Fits in the Family Tree

Selection sort belongs to the family of comparison-based sorts that work in-place with O(1) extra space. Its direct relatives: Bubble Sort and Insertion Sort. All three run O(n²) average and worst case. But they differ in how they move data.

Bubble Sort: Compares adjacent pairs and swaps when out of order. It's the slowest of the three — makes up to n passes with many swaps. Never use it. Seriously.

Insertion Sort: Builds sorted region by inserting one element at a time. Best case O(n) if data is nearly sorted. Makes fewer comparisons than selection sort on average, but more swaps. The go-to for small arrays (< 50 elements) in hybrid sorts like Timsort.

Heapsort: Uses a binary heap to extract the minimum in O(log n) time. Build heap O(n), then n extractions = O(n log n). Still in-place but not stable. It's selection sort on steroids — uses a smarter data structure to avoid the O(n) scan per element.

Quickselect: If you only need the k-th smallest element, not the full sort, use this. It's selection sort applied recursively with partitioning — O(n) average time. Don't waste time sorting to find a single element.

// io.thecodeforge — dsa tutorial

public class SortingRelativeCosts {
    public static void main(String[] args) {
        int[] worstCase = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int[] bestCase = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println("Selection on worst: " + countComparisons(worstCase) + " comps");
        System.out.println("Selection on best: " + countComparisons(bestCase) + " comps");
    }

    private static int countComparisons(int[] data) {
        int count = 0;
        int n = data.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                count++;
                if (data[j] < data[minIdx]) {
                    minIdx = j;
                }
            }
        }
        return count;
    }
}

Analysis: Why Selection Sort's Comparison Count Is a Fixed Cost You Can't Escape

Most devs think about Big O as an average-case abstraction. Selection Sort forces you to confront a brutal reality: the number of comparisons is always n(n-1)/2, regardless of input. That's not theory — that's a cold, hard lower bound. Every pass scans the entire unsorted portion to find the minimum. Even if the array is already sorted, you're making those comparisons. No early exit, no smart branch prediction. This fixed cost is why Selection Sort gets crushed by Insertion Sort on nearly-sorted data. But here's the trade-off: writes are minimal. Exactly n-3 swaps in the worst case. When you're writing to EEPROM or flash memory where each write cycle degrades the medium, that fixed comparison overhead is a price worth paying. The analysis isn't about speed — it's about knowing exactly what your algorithm commits to before it runs.

// io.thecodeforge — dsa tutorial

public class SelectionSortAnalysis {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        int comparisons = 0;
        int swaps = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                comparisons++;
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                int temp = arr[i];
                arr[i] = arr[minIdx];
                arr[minIdx] = temp;
                swaps++;
            }
        }
        System.out.println("Comparisons: " + comparisons);
        System.out.println("Swaps: " + swaps);
    }
    
    public static void main(String[] args) {
        int[] data = {64, 25, 12, 22, 11};
        selectionSort(data);
    }
}

Cache Behavior: Why Selection Sort Gut-Punches Your L1 Cache

Modern CPUs hate linear scans with random accesses. Selection Sort delivers both. The inner loop reads every element in the unsorted portion sequentially — that's cache-friendly. But the swap at the end writes to an arbitrary position you found earlier, blowing your cache line. For small arrays (under 100 elements), you won't feel it. For arrays that overflow your L1 cache (32KB on most x86), you'll see double-digit performance penalties compared to Insertion Sort. The killer: every pass reloads the entire unsorted segment. There's no locality reuse across passes. When you're sorting on embedded devices or in tight loops, this cache thrashing makes Selection Sort the worst choice even among O(n²) algorithms. The analysis isn't just about Big O — it's about what the hardware actually does. Cache misses cost 10-100x more cycles than a comparison.

// io.thecodeforge — dsa tutorial

public class CacheAwareSort {
    // Simulate cache-unfriendly behavior
    public static void selectionSortCache(int[] arr) {
        int n = arr.length;
        long cacheMisses = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
                // Every pass reads fresh memory — poor locality
                cacheMisses++;
            }
            // Swap writes to random location — cache line invalidation
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
        System.out.println("Approx cache misses: " + cacheMisses);
    }
    
    public static void main(String[] args) {
        int[] data = new int[2000];
        // Fill with random values
        for (int i = 0; i < data.length; i++) {
            data[i] = (int)(Math.random() * 10000);
        }
        selectionSortCache(data);
    }
}