These are the notes for DSA episode 16, the first episode of the sorting block (every binary search problem in episodes 12 to 15 needed sorted data). We build the three simple sorts everyone invents on their own: bubble sort (swap neighbours), selection sort (pick the smallest) and insertion sort (slot each value in, like playing cards). All three are correct, and all three are O(n²): two lakh random numbers time out. But insertion sort is adaptive: on ten lakh nearly sorted numbers it takes milliseconds. We also meet stability. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Morning assembly: the PT teacher wants a class of forty students in one line, shortest at the front. Nobody learned sorting, but everyone knows three ways to do it:
| In the school line | As an algorithm |
|---|---|
| Any two neighbours compare; the taller one steps back. Repeat until nobody swaps. | Bubble sort: compare a[j], a[j + 1], swap if out of order |
| The teacher picks the shortest and calls them to the front, then the shortest of the rest, ... | Selection sort: find the minimum, put it at position i |
| Students arrive one by one; each walks in from the back and stops behind someone shorter. Like sorting playing cards in your hand. | Insertion sort: shift bigger values right, drop the new value in |
Problem statement
Rearrange an array of integers into non-decreasing order: [5, 1, 4, 2, 8] → [1, 2, 4, 5, 8].
- In-place: sort inside the same array using O(1) extra space (a few variables).
- We compare sorts by counting comparisons and swaps (or shifts).
- Edge cases to test: an empty array, duplicates (
[3, 3, 1, 3]), already sorted input.
Bubble sort: swap neighbours
Walk left to right comparing each pair of neighbours; swap if the left one is bigger. After pass 1 the largest value has been carried ("bubbled") all the way to the end, so each pass can stop one place earlier. If a whole pass makes no swaps, the array is sorted: stop early.
| Pass | Swaps | Array after the pass |
|---|---|---|
| start | [5, 1, 4, 2, 8] | |
| 1 | 5↔1, 5↔4, 5↔2 (5 < 8: no swap) | [1, 4, 2, 5, 8] |
| 2 | 4↔2 | [1, 2, 4, 5, 8] |
| 3 | none → swapped = false → break |
[1, 2, 4, 5, 8] |
import java.util.*;
public class Main {
static void bubble(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swapped = true;
}
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] a = {5, 1, 4, 2, 8};
bubble(a);
System.out.println(Arrays.toString(a));
int[] e = {};
bubble(e);
System.out.println(Arrays.toString(e));
int[] d = {3, 3, 1, 3};
bubble(d);
System.out.println(Arrays.toString(d));
}
}
Output:
[1, 2, 4, 5, 8]
[]
[1, 3, 3, 3]
The inner loop stops at n - 1 - i: after i passes the last i values are final, and the loop reads a[j + 1], so it must stop one early.
Selection sort: pick the smallest
For each position i, scan the rest of the array for the minimum and swap it into position i. That value is now final and never moves again.
| i | Scan finds | Array after the swap |
|---|---|---|
| 0 | min 1 at index 1 | [1, 5, 4, 2, 8] |
| 1 | min 2 at index 3 | [1, 2, 4, 5, 8] |
| 2, 3 | already in place | [1, 2, 4, 5, 8] |
At most one swap per position (n - 1 in total): useful when moving an item is expensive. But the scan always compares everything: about n²/2 comparisons even on sorted input.
static void selection(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min]) min = j;
int t = a[i]; a[i] = a[min]; a[min] = t;
}
}
With the same main (calling selection) it printed [1, 2, 4, 5, 8], [], [1, 3, 3, 3].
Insertion sort: like playing cards
The left part a[0..i-1] is always sorted. Take the next value, the key a[i]; shift every bigger value in the sorted part one place right, then drop the key into the gap.
| Key | Shifts | Array after |
|---|---|---|
| 1 | 5 → right | [1, 5, 4, 2, 8] |
| 4 | 5 → right (1 < 4 stops) | [1, 4, 5, 2, 8] |
| 2 | 5 → right, 4 → right (1 < 2 stops) | [1, 2, 4, 5, 8] |
| 8 | none: one comparison | [1, 2, 4, 5, 8] |
A value that is already in place costs one comparison. That is the secret of insertion sort.
static void insertion(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
With the same main it printed [1, 2, 4, 5, 8], [], [1, 3, 3, 3].
The same three sorts in C++ and Python
#include <bits/stdc++.h>
using namespace std;
void bubble(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
if (!swapped) break;
}
}
void selection(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int mn = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[mn]) mn = j;
swap(a[i], a[mn]);
}
}
void insertion(vector<int>& a) {
for (int i = 1; i < (int)a.size(); i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
}
void show(const vector<int>& a) { for (int x : a) cout << x << " "; cout << "\n"; }
int main() {
vector<int> a = {5, 1, 4, 2, 8}, b = a, c = a;
bubble(a); selection(b); insertion(c);
show(a); show(b); show(c);
}
Output: 1 2 4 5 8 three times.
def bubble(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
def selection(a):
n = len(a)
for i in range(n - 1):
mn = i
for j in range(i + 1, n):
if a[j] < a[mn]:
mn = j
a[i], a[mn] = a[mn], a[i]
def insertion(a):
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
for f in (bubble, selection, insertion):
a = [5, 1, 4, 2, 8]
f(a)
print(f.__name__, a)
Output:
bubble [1, 2, 4, 5, 8]
selection [1, 2, 4, 5, 8]
insertion [1, 2, 4, 5, 8]
Two real out-of-bounds bugs
Bug 1: bubble sort's inner loop one step too far
for (int j = 0; j < n - i; j++)
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at Main.bubble(Main.java:9)
On the first pass j reaches 4 and a[j + 1] is a[5], one past the end. A loop that reads a[j + 1] must stop at n - 1 - i.
Bug 2: insertion sort's condition in the wrong order
while (a[j] > key && j >= 0) {
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
at Main.insertion(Main.java:7)
When the key is the smallest so far, j walks down to -1 and a[-1] is read before the j >= 0 check. && stops at the first false part (short-circuit evaluation), so put j >= 0 first.
The big input: why all three are O(n²)
Two lakh random numbers:
int n = 200000;
int[] a = new int[n];
Random r = new Random(1);
for (int i = 0; i < n; i++) a[i] = r.nextInt(1000000);
long t0 = System.nanoTime();
bubble(a);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(a[0] + " " + a[n - 1] + " " + ms + " ms");
bubble(a): Time Limit Exceededinsertion(a): Time Limit Exceededselection(a): Time Limit ExceededArrays.sort(a)(for comparison):1 999988 134 ms
| n | about n² / 2 comparisons | |
|---|---|---|
| 1,000 | 5 lakh | instant |
| 10,000 | 5 crore | fine |
| 2 lakh | 2 × 10¹⁰ | minutes |
Ten times more numbers means a hundred times more work. The reason is the same for all three: every step does a tiny bit of work. It places one value, or swaps one pair of neighbours, so a value far from home moves one place per swap and may need up to n moves. n values × up to n steps = O(n²). To beat it you need a new idea: split the array, sort the halves, merge (merge sort, next episode). On random data insertion sort does about n²/4 shifts: half of bubble's work, still O(n²).
Nearly sorted? Insertion sort takes milliseconds
Ten lakh numbers, already sorted except that every thousandth pair is swapped (like a register where a few students swapped seats):
int n = 1000000;
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i;
for (int i = 0; i + 1 < n; i += 1000) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
long t0 = System.nanoTime();
insertion(a);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(a[0] + " " + a[n - 1] + " " + ms + " ms");
Output (timing varies from run to run):
0 999999 28 ms
Five times more numbers than the input that timed out, sorted in milliseconds. Insertion sort costs O(n + number of inversions) (an inversion is a pair i < j with a[i] > a[j]); nearly sorted data has few inversions, so it is close to O(n). This is called adaptive, and it is why real library sorts (Java's TimSort for objects, C++'s introsort) switch to insertion sort for small or nearly sorted pieces.
Stable sorting
The register is in roll-number order: Asha (section B), Ravi (A), Neha (B), Imran (A). The office sorts it by section only. A stable sort keeps students with the same section in their old order (Ravi before Imran, Asha before Neha); an unstable sort may not.
import java.util.*;
public class Main {
static void selection(String[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++)
if (a[j].charAt(0) < a[min].charAt(0)) min = j;
String t = a[i]; a[i] = a[min]; a[min] = t;
}
}
static void insertion(String[] a) {
for (int i = 1; i < a.length; i++) {
String key = a[i];
int j = i - 1;
while (j >= 0 && a[j].charAt(0) > key.charAt(0)) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
public static void main(String[] args) {
String[] s1 = {"B-Asha", "A-Ravi", "B-Neha", "A-Imran"};
String[] s2 = s1.clone();
selection(s1);
insertion(s2);
System.out.println(Arrays.toString(s1));
System.out.println(Arrays.toString(s2));
}
}
Output:
[A-Ravi, A-Imran, B-Neha, B-Asha]
[A-Ravi, A-Imran, B-Asha, B-Neha]
Selection sort is not stable: its first long-distance swap moved B-Asha to index 1, and the second moved her behind B-Neha. Insertion sort is stable: it only moves past strictly bigger keys. Bubble sort is stable too, as long as it swaps only on > (never >=).
Complexity
| Sort | Best | Average | Worst | Swaps / moves | Extra space | Stable | Adaptive |
|---|---|---|---|---|---|---|---|
| Bubble (with flag) | O(n) | O(n²) | O(n²) | up to n²/2 swaps | O(1) | yes | yes |
| Selection | O(n²) | O(n²) | O(n²) | n - 1 swaps | O(1) | no | no |
| Insertion | O(n) | O(n²) | O(n²) | about n²/4 shifts on random data | O(1) | yes | yes |
When to use which: insertion sort for small arrays (a few dozen elements) and nearly sorted data; selection sort when writes are very expensive; bubble sort mostly for teaching. For big random data, use an O(n log n) sort.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
for (j = 0; j < n - i; j++) ... a[j + 1] |
ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5 |
a[j + 1] is past the end |
j < n - 1 - i |
while (a[j] > key && j >= 0) |
ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5 |
a[j] read before the check |
j >= 0 && a[j] > key |
Bubble sort without the swapped flag |
sorted input still costs n²/2 comparisons | no early exit | break when a pass swaps nothing |
| Swapping inside selection's inner loop | many swaps; it becomes a slow exchange sort | swap only after the scan | remember min, swap once |
a[j] >= a[j + 1] in bubble sort |
still sorted, but unstable (equal keys swap) | swaps equal values | use > |
| Expecting a simple sort to pass n = 10⁵ | Time Limit Exceeded | O(n²) | an O(n log n) sort |
Mini project: the assembly line-up
Read students as name height pairs and print them sorted by height with insertion sort, keeping roll-number order for equal heights (stability). Print the number of shifts it made. Then shuffle only two students and sort again: compare the shift counts and explain the difference with the word "adaptive".
Practice
- Sort in descending order with insertion sort.
Solution
Flip one comparison: while (j >= 0 && a[j] < key). For [5, 1, 4, 2, 8] it printed [8, 5, 4, 2, 1].
- How many swaps does bubble sort make on
[5, 1, 4, 2, 8]?
Solution
4: three in pass 1 (5↔1, 5↔4, 5↔2) and one in pass 2 (4↔2). A counter swaps++ inside the if printed 4. (The number of swaps always equals the number of inversions.)
- Make selection sort stable.
Solution
Instead of swapping a[i] and a[min], take a[min] out and shift a[i..min-1] one place right, then put it at i:
String key = s[min];
for (int k = min; k > i; k--) s[k] = s[k - 1];
s[i] = key;
On the register it printed [A-Ravi, A-Imran, B-Asha, B-Neha]. It now does O(n²) moves instead of n - 1 swaps.
- Binary insertion sort: find the key's spot with binary search. Does it make insertion sort O(n log n)?
Solution
No. Binary search (an upper bound, to stay stable) cuts comparisons to O(n log n), but the values still have to be shifted one by one, which is O(n²) in the worst case.
Quick quiz
How many passes does bubble sort (with the swapped flag) make on {1, 2, 3, 4, 5}?
- 1
- 4
- 5
- 0
Answer
1. The first pass compares 4 pairs, swaps nothing, so swapped stays false and the loop breaks: 4 comparisons, the O(n) best case.
Interview questions
- Which simple sort would you use for nearly sorted data, and why? Insertion sort: O(n + inversions), close to O(n).
- Which one makes the fewest swaps? Selection sort: at most n - 1.
- Which are stable? Bubble and insertion (with strict
>); selection is not. - What does in-place mean? O(1) extra memory; all three are in-place.
- Why are they O(n²)? Each step fixes one value or swaps one neighbour pair; a value far from home needs up to n moves.
- What is the best case of bubble sort? O(n) with the early-exit flag, on sorted input; without the flag, O(n²).
- Why do library sorts use insertion sort inside? For small pieces (around 16 to 32 elements) its low overhead beats the fast sorts.
Glossary
| Term | Meaning |
|---|---|
| Sorting | Rearranging values into order, here non-decreasing |
| Comparison | Checking which of two values is bigger |
| Swap | Exchanging two values, using a temporary variable t |
| Shift | Moving a value one place right to make room |
| Pass | One full walk through (part of) the array |
| Bubble sort | Repeatedly swapping out-of-order neighbours; the biggest value "bubbles" to the end each pass |
| Selection sort | Repeatedly selecting the minimum of the unsorted part and swapping it into place |
| Insertion sort | Inserting each new value into the sorted part on its left |
| Key | The value being inserted in insertion sort |
| In-place | Uses O(1) extra memory |
| Stable | Equal keys keep their original relative order |
| Adaptive | Runs faster when the input is already nearly sorted |
| Inversion | A pair i < j with a[i] > a[j]; a sorted array has none |
| O(n²) | Work grows with the square of n: 10× the data, 100× the time |
| Short-circuit evaluation | && stops at the first false part, so later parts are not evaluated |
ArrayIndexOutOfBoundsException |
Java's runtime error for an index outside 0..length-1 |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- Bubble sort swaps neighbours and stops when a pass swaps nothing; selection sort picks the minimum (n - 1 swaps); insertion sort shifts bigger values right and drops the key in.
- Loop bounds:
j < n - 1 - iwhen readinga[j + 1];j >= 0 && a[j] > keyin that order. - All three are O(n²) on random data: two lakh numbers time out.
- Insertion sort is adaptive (near O(n) on nearly sorted data) and stable; selection sort is not stable.
- All three are in-place with O(1) extra space.
Next episode: Merge sort and counting inversions.