Comparison Sorting

1. Introduction

What are Elementary Comparison Sorts?

Elementary Comparison Sorts refer to Bubble Sort, Selection Sort, and Insertion Sort. These algorithms solve sorting by comparing adjacent or distant elements, performing swaps or shifts until the collection is fully ordered.

Why study them?

While modern applications use O(N log N) sorting algorithms, these O(N²) algorithms are critical because:

They are incredibly simple to understand and implement.

They have no recursive stack overhead.

Insertion Sort is highly efficient for small arrays (typically fewer than 15-32 elements) and serves as the baseline step for state-of-the-art hybrid algorithms like Timsort and Introsort.

---

2. Mental Models

Bubble Sort: Bubbles Rising

Think of elements as gas bubbles in water. The larger, heavier elements "sink" to the bottom, while the smaller, lighter elements "rise" to the top. In each pass through the array, adjacent pairs are compared, and the larger element is swapped forward. By the end of the first pass, the largest element is locked at the end of the array.

Selection Sort: Scanning for the Smallest

Imagine sorting a stack of books by size. You scan the entire messy stack to find the absolute smallest book, then swap it with the book at the very first position. Then you scan the remaining books to find the second smallest, swap it to the second position, and so on.

Insertion Sort: Organizing a Hand of Cards

Imagine you are being dealt playing cards one by one. You hold a sorted hand. When you receive a new card (e.g., a 7), you scan your sorted hand from right to left, shifting larger cards (e.g., 8, 9, 10) to the right to make room, and then insert the 7 into its correct sorted position.

---

3. Core Concepts & Implementations

Let's dive into the implementations of each comparison sort.

1. Bubble Sort (With Early-Exit Optimization)

Without optimization, Bubble Sort always runs in O(N²) time. By adding a boolean flag swapped, we can terminate the algorithm early if a full pass occurs without any swaps (indicating the array is already sorted).

2. Selection Sort

Selection Sort divides the array into sorted and unsorted regions. It repeatedly finds the minimum element from the unsorted region and swaps it to the front. Because it always performs N² comparisons, its time complexity is always O(N²), but it minimizes the number of writes (at most N swaps).

3. Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It is highly efficient for small datasets and partially sorted arrays (O(N) best case).

---

4. Visuals & Trace

Let's look at how Insertion Sort processes the input array [5, 2, 9, 1]:

Comparative Analysis Table

---

5. Real-World Applications

Timsort & Introsort Base Cases: Standard libraries drop down to Insertion Sort once subarrays during Merge/Quick Sort divide stages drop below 15-32 elements, saving recursive overhead.

Online Sorting / Continuous Input: Insertion Sort is optimal if you receive data one by one and need to maintain a sorted state constantly (e.g., high-frequency scoreboard ranking).

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers rarely ask you to implement Bubble Sort straight, but they evaluate your understanding of their mechanics:

"Implement an algorithm to sort elements with minimal writes." -> Selection Sort (only O(N) swaps).

"Sort a list where each element is at most K positions away from its target sorted location." -> Use Insertion Sort (O(N × K) complexity, which is O(N) if K is small!).

Common Mistakes

> 2. Forgetting to Optimize Bubble Sort: Writing a basic nested Bubble Sort loop that always performs (N²)/2 checks even on fully sorted input shows a lack of complexity optimization.

---

7. Summary

Bubble Sort: Simplest adjacent-pair swapping. Can exit early using a swapped flag.

Selection Sort: Unstable, but has the advantage of minimizing physical swaps in memory to at most N.

Insertion Sort: The king of elementary sorts. Adaptive, stable, and widely used to optimize standard libraries for small chunks.

---

8. Quiz

Question 1: Which of the elementary sorting algorithms is adaptive and runs in O(N) time when the array is already sorted?

Answer: Insertion Sort (and optimized Bubble Sort). Insertion Sort's inner loop checks arr[j] > key. If the array is already sorted, this condition fails immediately on the first check, resulting in a single pass of O(N) operations.

Question 2: What is the primary advantage of Selection Sort over Insertion Sort?

Answer: Selection Sort minimizes the number of swap/write operations. It makes at most N - 1 swaps, whereas Insertion Sort can make up to O(N²) shifts/writes in the worst case. This is useful for EEPROMs or flash memory where writes are slow or wear down hardware.

Question 3: Why is standard Selection Sort considered unstable? Give a simple counter-example.

Answer: Selection Sort swaps elements over long distances. Example: [5a, 5b, 2]. The minimum is 2. Selection sort swaps 5a with 2, resulting in [2, 5b, 5a]. The relative order of the identical elements 5 is reversed.

Question 4: In a hybrid algorithm like Timsort, why is Insertion Sort used for sorting small subarrays instead of Quick/Merge Sort?

Answer: Because Quick/Merge Sort have recursive call overhead, function frame allocations, and metadata structures. For small N (e.g., N ≤ 16), the constant factor of Insertion Sort is so small that it runs faster than recursive partitioning/splitting.

Question 5: If you are sorting an array that is almost sorted (only a few elements out of place), which elementary sort is best?

Answer: Insertion Sort. It will run in near-linear O(N) time because the inner shifting loop will exit almost immediately for most elements.