Elementary Sorts

Sorted data unlocks binary search, two pointers and easy duplicate detection. The three simple sorts are where every programmer learns what "O(n²)" feels like.

★ Lecture: sorting_insertion · Zaza Gamezardashvili▶ video beginner⏱ 10 min read

←Builds on

1Arrays & Dynamic ArraysEvery elementary sort swaps elements in place inside one array.0Big-O & Growth RatesCounting comparisons in two nested loops shows why these sorts are O(n²).

Leads to→

2Merge Sort: Divide & ConquerSplitting the work in half is what beats the O(n²) of the elementary sorts.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01Bubble sort: swap neighbours

Walk through the array and compare each pair of neighbours. If they are in the wrong order, swap them.

After one full pass, the largest value has been carried all the way to the end, like a bubble rising to the surface. It is now in its final place, so the next pass can stop one step earlier.

The invariant: after pass k, the last k positions hold the k largest values in order. Repeat n − 1 passes and everything is sorted. If a pass makes no swaps, the array is already sorted and you can stop early; that makes bubble sort O(n) on sorted input.

02Selection sort: pick the minimum

Keep a sorted prefix on the left. In each round, scan the unsorted part, find its minimum, and swap it to the front of the unsorted part. The sorted prefix grows by one.

Selection sort always does about n²/2 comparisons, even on sorted input: it has to scan to be sure it found the minimum. Its one advantage is that it makes at most n − 1 swaps, which matters only when writing is very expensive.

It is not stable: a swap over a long distance can jump an element over an equal one.

03Insertion sort: like sorting cards in your hand

Take the next element and slide it left into the sorted part: every bigger value shifts one step right until the gap is in the right place.

Worst case (reversed input) it shifts every element past all previous ones: O(n²). But on nearly sorted data each element moves only a little, and insertion sort runs in about O(n + inversions), close to linear.

That is why real libraries use it: std::sort and Python's Timsort switch to insertion sort for small pieces (around 16 elements in std::sort, 32 to 64 in Timsort), where its tiny constant beats everything else. It is also stable and sorts in place.

04Why O(n²) is the baseline to beat

All three sorts fix the order by moving elements a short distance at a time. A reversed array has about n²/2 pairs out of order (inversions), and swapping neighbours removes only one inversion per swap. So any "swap neighbours" method needs O(n²) work in the worst case.

For n = 1000 that is fine. For n = 10⁵ it is about 5·10⁹ steps: far too slow. To do better, an algorithm has to move elements far in one step, which is exactly what merge sort and quicksort do, reaching O(n log n).

In practice you will rarely write these three by hand, but their ideas reappear: the bubble invariant, selection's "find the min" and insertion into a sorted part.

Cost at a glance

Bubble (worst / sorted input)O(n²) / O(n)

Selection (always)O(n²)

Insertion (worst / nearly sorted)O(n²) / ≈O(n)

Extra memoryO(1)

Remember

Bubble, selection and insertion sort all cost O(n²) in the worst case because they move elements only a short distance at a time.
Each keeps an invariant: a sorted part that grows by one element per round.
Insertion sort is fast on nearly sorted or tiny arrays, which is why real libraries still use it.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the sorted suffix grow by one after every pass. Then switch the algorithm field to selection or insertion and run the same numbers: count how many swaps each one needs. Try an already sorted input too.

Interactive visualizerfocus here, then space ← →

Bubble sort

comparingsorted suffix

Sort 8 elements. Each pass "bubbles" the largest remaining value to the end of the unsorted prefix.

Pseudocode

 1 for i in 0..n-2:            // passes 2   for j in 0..n-2-i: 3     if a[j] <= a[j+1]: keep order 4     else: swap(a[j], a[j+1]) 5   // largest of the pass has "bubbled" to the end 6 // selection sort 7 for i in 0..n-2: 8   m = i                // smallest seen so far 9   for j in i+1..n-1: if a[j] < a[m]: m = j10   swap(a[i], a[m])     // a[i] is final11 // insertion sort12 for i in 1..n-1:13   key = a[i]; j = i-114   while j >= 0 and a[j] > key: a[j+1] = a[j]; j--15   a[j+1] = key         // a[0..i] is sorted

1 / 1

Check

Three questions. Pick an answer to see why.

After the first bubble sort pass on [5, 1, 4, 2, 8, 3], what is the array?

Your data is already sorted except for a few elements near the end. Which simple sort fits best?

Why must any sort that only swaps adjacent elements be O(n²) in the worst case?

Practice

Real problems to lock it in, easiest first.

LeetCodeHeight Checker beginner↗LeetCodeSquares of a Sorted Array beginner↗LeetCodeInsertion Sort List intermediate↗LeetCodeSort Colors intermediate↗