📊 Basic Sorting: O(n²) Fundamentals

While modern systems use advanced sorting algorithms, understanding the basic $O(n^2)$ variants is crucial for building algorithmic intuition.

💡 The Logic (ELI5)

1. Bubble Sort (The Heavy Rise)

Think of bubbles in a soda. The largest bubbles rise to the top first. You compare adjacent elements and swap them if they are in the wrong order. After the first pass, the largest element is at the end.

2. Selection Sort (The Smallest Pick)

Think of picking teams. You look at the whole line, find the smallest person, and put them at the front. Then you look at the remaining line, find the next smallest, and repeat.

3. Insertion Sort (The Hand of Cards)

Think of sorting a hand of cards. You pick one card at a time and "insert" it into its correct position among the cards you're already holding.

🔍 The Deep Dive

Comparison Table

Algorithm	Best Time	Avg Time	Space	Stable?
Bubble	$O(n)$	$O(n^2)$	$O(1)$	Yes
Selection	$O(n^2)$	$O(n^2)$	$O(1)$	No
Insertion	$O(n)$	$O(n^2)$	$O(1)$	Yes

🛠️ Code Forge: Insertion Sort

Insertion Sort is the most "practical" of the three because it's very fast for nearly sorted data.


javascript Standard
/**
 * Insertion Sort - O(n^2)
 */
function insertionSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    let current = nums[i];
    let j = i - 1;

    // Shift elements of nums[0..i-1] that are greater than current
    while (j >= 0 && nums[j] > current) {
      nums[j + 1] = nums[j];
      j--;
    }
    nums[j + 1] = current;
  }
  return nums;
}

🎯 Interview Pulse

Why learn these?

Small Datasets: Insertion sort can be faster than Quicksort for very small arrays (e.g., $n < 20$).
Concept of Stability: A "Stable" sort preserves the relative order of equal elements. Bubble and Insertion are stable; Selection is not.
Online Sorting: Insertion sort can sort data as it's being received (stream of data).

Common Questions

Explain the difference between Selection and Bubble Sort.
When would you use Insertion Sort over Merge Sort?
Implement a version of Bubble Sort that stops early if the array is already sorted ($O(n)$ best case).