Basic Sorts

[!NOTE] This module explores the core principles of Basic Sorts, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: Why learn specific slow algorithms?

In an age of O(N log N) super-algorithms, why bother with O(N²) dinosaurs?

1. Hardware Reality: For small N (e.g., N < 32), the overhead of recursion and complex logic in Quicksort makes it slower than Insertion Sort. This is why standard libraries (like Python’s Timsort or Java’s Arrays.sort) switch to Insertion Sort for small chunks.
2. Properties: Insertion Sort is Online (can sort data as it arrives). Bubble Sort is capable of detecting an already sorted list in O(N).

---

2. The 3 Quadratic Kings

A. Bubble Sort

Intuition: “Bubbling” the largest element to the top (end) in each pass.

• Invariant: After k iterations, the last k elements are sorted and in their final positions.
• Best Case: O(N) (if already sorted and using a swapped flag).
• Worst Case: O(N²).

B. Selection Sort

Intuition: “Selecting” the smallest element from the unsorted portion and swapping it to the front.

• Invariant: After k iterations, the first k elements are sorted.
• Writes: Minimizes writes (at most N swaps). Useful when writing to memory is expensive (e.g., Flash memory).
• Stability: Not Stable by default (can swap duplicate elements past each other).

C. Insertion Sort

Intuition: Ordering a hand of playing cards. Pick the next card and insert it into the correct spot in the sorted hand.

• Invariant: After k iterations, the first k elements are relative-sorted (but not necessarily in final geometric position).
• Real World: Extremely fast for “almost sorted” arrays (O(N)).
• Hardware: Very cache-friendly linear scans.

---

3. Interactive: Compare the Mechanics

Watch how the algorithms process the array differently.

• Bubble: Large bars race to the right.
• Selection: The left side slowly builds up, strictly in order.
• Insertion: Elements “dive” into the sorted left portion.

Idle

---

4. Implementation: Insertion Sort (Java & Go)

Insertion sort is the most useful of the three for production code (as a base case).

public void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;

    // Move elements of arr[0..i-1] that are greater than key
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

func InsertionSort(arr []int) {
  for i := 1; i < len(arr); i++ {
    key := arr[i]
    j := i - 1

    // Move elements that are greater than key
    for j >= 0 && arr[j] > key {
      arr[j+1] = arr[j]
      j = j - 1
    }
    arr[j+1] = key
  }
}

5. Hardware Reality: Branch Prediction

Why is Bubble Sort so slow? It involves a conditional swap if (arr[j] > arr[j+1]). In a random array, this branch is taken 50% of the time. This is the worst case for branch predictors. The CPU pipeline flushes constantly.

Insertion Sort, on “almost sorted” data, has a very predictable branch (mostly “false” for the inner loop condition), making it fly through the pipeline.

---