This is the second post in the sorting series, focusing on three O(n^2) baseline algorithms: bubble, selection, and insertion. They are simple and foundational, useful for understanding higher-level sorts and still valuable on small or nearly sorted data.

Target Readers

  • Practice and teaching: need to master baseline sorts and explain them.
  • Engineers: small-scale, embedded, or code-size-sensitive scenarios.
  • Learners: want to understand stability, in-place behavior, and complexity sources.

Background and Motivation

  • Pain points:
    • O(n^2) sorts are often ignored, but they represent the three core ideas: swap, select, insert.
    • On small or nearly sorted data, insertion sort can outperform O(n log n) algorithms.
    • We need a side-by-side comparison of stability, swaps/moves, and engineering use.

A - Algorithm

Theme: Compare bubble (swap-driven), selection (min selection), and insertion (prefix insertion) with a basic example.

Example array: [5, 2, 4, 6, 1]

  • Bubble: adjacent swaps bubble the max to the end; repeat n passes.
  • Selection: pick min each pass and swap into place; at most n swaps.
  • Insertion: maintain a sorted prefix and insert current element; efficient when nearly sorted.

Illustration (first two insertion passes):

Pass 1: |5| 2 4 6 1 -> 2 5 4 6 1
Pass 2: 2 |5| 4 6 1 -> 2 4 5 6 1

C - Concepts

AlgorithmIdeaStableIn-placeComparisons (avg)Swaps/Moves
BubbleAdjacent swapsYesYesO(n^2)O(n^2) swaps
SelectionSelect min each passNoYesO(n^2)O(n) swaps
InsertionInsert into sorted prefixYesYesO(n^2)O(n^2) moves; O(n) when nearly sorted

Where they fit

  • Bubble: teaching, stability requirement, tiny arrays.
  • Selection: high swap cost (large objects), comparisons are acceptable.
  • Insertion: small arrays, nearly sorted; also used as a subroutine in TimSort/Shell.

E - Engineering

Scenario 1: Embedded firmware small arrays (C)

Background: microcontroller sorting at most tens of integers. Why: short code, in-place, no extra memory; selection sort has few swaps.

// Selection sort, in-place O(1) space
void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_i = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[min_i]) min_i = j;
        if (min_i != i) {
            int tmp = a[i]; a[i] = a[min_i]; a[min_i] = tmp;
        }
    }
}

Scenario 2: Nearly sorted small lists (Python)

Background: UI list receives a few new items; data is mostly ordered. Why: insertion sort runs close to O(n) when inversions are small.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

data = [1, 2, 3, 5, 4]
print(insertion_sort(data))

Scenario 3: Teaching visualization (JavaScript)

Background: show swap vs insert in a classroom or demo. Why: bubble sort is stable and intuitive; JS is short and visual.

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]];
        swapped = true;
      }
    }
    if (!swapped) break; // small optimization
  }
  return a;
}
console.log(bubbleSort([5, 2, 4, 6, 1]));

Scenario 4: Small batch sorting (Go)

Background: request payload size < 64, prefer smaller constants. Why: Go sort switches to insertion for small segments; show a minimal implementation.

package main

import "fmt"

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        key := a[i]
        j := i - 1
        for j >= 0 && a[j] > key {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = key
    }
}

func main() {
    arr := []int{5, 2, 4, 6, 1}
    insertionSort(arr)
    fmt.Println(arr)
}

R - Reflection

  • Complexity: all three have O(n^2) time in worst/avg, O(1) space.
  • Stability: bubble and insertion are stable; selection is not (swap can break order).
  • Alternatives:
    • Small arrays: insertion beats bubble/selection; also used as fallback in TimSort/Introsort.
    • Large arrays: switch to O(n log n) (quick/merge/heap) or non-comparison.
  • Why keep them:
    • Teaching value: clear view of comparisons, swaps, and moves.
    • Engineering value: tiny input, nearly sorted, code size constraints, or as hybrid submodules.

S - Summary

  • Bubble/selection/insertion represent swap/select/insert ideas and are core to understanding sorting.
  • Stability: bubble and insertion are stable; selection is not but uses few swaps.
  • On small or nearly sorted data, insertion often beats O(n log n) algorithms.
  • Modern sort implementations use hybrids: large segments use quick/heap/merge, small segments fall back to insertion.
  • Choose based on size, degree of order, stability, and swap cost.

Practice Guide / Steps

  • If n < 64 and nearly sorted, prefer insertion.
  • Need stability and visualization: bubble with early-exit optimization.
  • Swap cost is high: selection reduces swaps.
  • Use insertion as a subroutine in quick/merge for small segments.

Runnable Examples (Multilang Baselines)

Python - Insertion

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]; j -= 1
        a[j+1] = key
    return a

print(insertion_sort([5,2,4,6,1]))

C - Selection

void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_i = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[min_i]) min_i = j;
        if (min_i != i) { int t=a[i]; a[i]=a[min_i]; a[min_i]=t; }
    }
}

C++ - Bubble

#include <bits/stdc++.h>
using namespace std;
void bubble(vector<int>& a){
    for(size_t i=0;i<a.size();++i){
        bool swapped=false;
        for(size_t j=0;j+1<a.size()-i;++j){
            if(a[j]>a[j+1]){swap(a[j],a[j+1]);swapped=true;}
        }
        if(!swapped) break;
    }
}
int main(){vector<int> a={5,2,4,6,1}; bubble(a); for(int x:a) cout<<x<<" ";}

Go - Insertion

func insertion(a []int){
    for i:=1;i<len(a);i++{
        key:=a[i]; j:=i-1
        for j>=0 && a[j]>key { a[j+1]=a[j]; j-- }
        a[j+1]=key
    }
}

Rust - Insertion

fn insertion_sort(a: &mut [i32]) {
    for i in 1..a.len() {
        let key = a[i];
        let mut j = i as i32 - 1;
        while j >= 0 && a[j as usize] > key {
            a[(j+1) as usize] = a[j as usize];
            j -= 1;
        }
        a[(j+1) as usize] = key;
    }
}

fn main(){
    let mut v = vec![5,2,4,6,1];
    insertion_sort(&mut v);
    println!("{:?}", v);
}

JavaScript - Bubble

function bubbleSort(a){
  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;
  }
  return a;
}
console.log(bubbleSort([5,2,4,6,1]));

Explanation and Trade-offs

  • Bubble vs Selection: bubble is stable but swaps more; selection swaps less but is unstable.
  • Insertion vs Bubble: insertion does fewer moves; nearly sorted arrays can drop to O(n).
  • Hybrid strategy: quick/heap for large segments, insertion for small segments.

Common Pitfalls and Notes

  • Bubble without early exit wastes O(n^2) on already sorted input.
  • Selection with large structs: fewer swaps but each swap is costly; for stability use index arrays.
  • Insertion degrades on large arrays; best for small or nearly sorted segments.

Best Practices

  • Keep a comparison table for stability, swaps/moves, and constants.
  • Write an insertion helper and reuse it in custom quick/merge sorts.
  • Test with sorted, reversed, many duplicates, and nearly sorted to observe early-exit behavior.

Conclusion

  • The O(n^2) trio is the foundation and a key component of hybrid sorting.
  • For nearly sorted or small inputs, insertion remains a strong choice.
  • Stable needs -> bubble or insertion; swap cost sensitive -> selection or stable variants.

References and Further Reading

  • CLRS chapters on insertion/bubble/selection sort
  • CPython TimSort implementation notes (insertion thresholds)
  • Intel/AMD notes on cache effects for small array sorting

Meta

  • Reading time: approx. 14 min
  • SEO keywords: bubble sort, selection sort, insertion sort, O(n^2) sorting, stability
  • Meta description: sorting series (2) comparing bubble/selection/insertion principles, stability, scenarios, and multilingual implementations for small or nearly sorted data.

Call to Action (CTA)

  • Benchmark a small dataset (e.g., 50 log rows) with all three algorithms.
  • Add a “<= 32 switch to insertion” optimization in your quick/merge and measure the gain.
  • Follow the series: shell, merge, quick, heap, non-comparison, TimSort/Introsort, selection guide.