Bubble, Selection & Insertion Sort

Before diving into efficient sorting algorithms, it helps to understand the simple O(n²) sorts. They’re slow on large inputs, but they’re easy to reason about, have tiny overhead, and two of them (insertion sort in particular) are still used in practice for small or nearly-sorted arrays.

Bubble Sort

Bubble sort repeatedly walks through the array, comparing adjacent pairs and swapping them if they’re out of order. After each pass, the largest unsorted element “bubbles up” to its correct position at the end.

function bubbleSort(arr: number[]): number[] {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    let swapped = false;
    for (let j = 0; j < a.length - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted — early exit
  }
  return a;
}

One Pass of Bubble Sort (visualized)

graph LR
  A["[5, 3, 8, 1]"] -->|"compare 5,3 → swap"| B["[3, 5, 8, 1]"]
  B -->|"compare 5,8 → no swap"| C["[3, 5, 8, 1]"]
  C -->|"compare 8,1 → swap"| D["[3, 5, 1, 8]"]
  D -->|"8 is in place"| E["End of pass 1"]

After pass 1, 8 is in its final position. After pass 2, 5 will be. And so on.

Selection Sort

Selection sort divides the array into a sorted left portion and an unsorted right portion. On each pass it scans the unsorted portion to find the minimum element, then swaps it into the next sorted position.

function selectionSort(arr: number[]): number[] {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    let minIdx = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
  return a;
}

Selection sort always makes exactly n−1 swaps regardless of input order. This makes it useful when writes are expensive (e.g., writing to flash memory) even though it’s still O(n²) in time.

Insertion Sort

Insertion sort builds a sorted sub-array from left to right. For each new element, it slides it left past any elements that are larger, inserting it in the right spot — like sorting playing cards in your hand.

function insertionSort(arr: number[]): number[] {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    const key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}

Side-by-Side Complexity

Stable means equal elements maintain their original relative order — important when you’re sorting objects by one field and want to preserve a previous sort on another field.

When to Use Each

• Bubble sort — teaching tool; rarely used in production
• Selection sort — when minimizing writes matters more than speed
• Insertion sort — small arrays, nearly-sorted data, or as the base case inside faster algorithms

Further Learning

Search these terms to go deeper:

• “Visualgo sorting visualizations” — animated, step-by-step views of all three algorithms
• “Insertion sort nearly sorted performance” — explains why O(n) best-case matters in practice
• “Sorting algorithms comparison geeksforgeeks” — side-by-side code and analysis
• “TimSort Python Java sorting” — the hybrid algorithm that uses insertion sort for small runs

Bubble, Selection & Insertion Sort

Before the fast, clever sorting algorithms, it helps to meet three simple ones. They’re slow on big lists, but they’re easy to picture — and each mirrors a way you’d sort things by hand. All three are O(n²) (a loop inside a loop), so they’re for learning and small lists.

Bubble sort — swap neighbors

Walk through the list comparing each pair of neighbors, swapping them if they’re in the wrong order. Big values slowly “bubble” to the end. Repeat until no swaps are needed.

function bubbleSort(arr) {
  const a = [...arr]
  for (let i = 0; i < a.length; i++) {
    let swapped = false
    for (let j = 0; j < a.length - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]]  // swap
        swapped = true
      }
    }
    if (!swapped) break  // already sorted — stop early
  }
  return a
}

Selection sort — find the smallest, place it

Scan the whole unsorted part to find the smallest value, then put it at the front. Repeat with the rest. It’s like laying out cards by repeatedly picking the lowest.

function selectionSort(arr) {
  const a = [...arr]
  for (let i = 0; i < a.length; i++) {
    let min = i
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[min]) min = j
    }
    [a[i], a[min]] = [a[min], a[i]]
  }
  return a
}

Insertion sort — like sorting cards in your hand

This is the one you actually do in real life. Take each new card and slide it left until it’s in the right spot among the cards you’ve already sorted:

function insertionSort(arr) {
  const a = [...arr]
  for (let i = 1; i < a.length; i++) {
    const key = a[i]
    let j = i - 1
    while (j >= 0 && a[j] > key) {  // slide bigger items right
      a[j + 1] = a[j]
      j--
    }
    a[j + 1] = key  // drop the card into place
  }
  return a
}

Quick comparison

In one sentence

Bubble sort swaps neighbors, selection sort repeatedly grabs the smallest, and insertion sort slides each item into place like sorting cards — all simple, all O(n²), best kept for small or nearly-sorted lists.

Want to go deeper?

Switch to Expert mode above for the full complexity table, the meaning of “stable” sorting, and where each one is used in practice.