Bubble sort, selection sort and insertion sort are the three simple O(n²) sorts. Bubble swaps neighbours until the largest values sink to the end; selection finds the smallest remaining value and puts it next; insertion takes each new value and slides it into the sorted part on the left.
| Bubble | Selection | Insertion | |
|---|---|---|---|
| Best case | O(n²), or O(n) with early exit | O(n²) | O(n) |
| Average case | O(n²) | O(n²) | O(n²) |
| Worst case | O(n²) | O(n²) | O(n²) |
| Extra space | O(1) | O(1) | O(1) |
| Stable? | Yes | No (as written) | Yes |
| Swaps / writes | Up to about n²/2 | At most n−1 | One write per shift |
| Good at | Teaching; already-sorted data with early exit | Few writes | Small or nearly sorted arrays |
This page traces each one pass by pass on the same input, [5, 1, 4, 2, 8], then counts comparisons and swaps on 1,000 elements, and ends with a stability test that shows why selection sort (as written here) is not stable.
Tested on OpenJDK 21.0.12. Every trace and count on this page is real output from SimpleSorts.java. The program also checks that all three algorithms produce the same result as Arrays.sort on 1,000 random values.
Bubble sort
Compare each pair of neighbours and swap if they are out of order. After pass 1 the largest value is at the end, after pass 2 the second largest is in place, and so on, so each pass can stop one position earlier.
The diagram follows pass 1 on 5 1 4 2 8. The 5 is bigger than everything it meets, so it is swapped three times and travels right until it hits the 8. That is the “bubble”: large values rise to the end.
static void bubbleSort(int[] a) {
int n = a.length;
for (int pass = 1; pass < n; pass++) {
for (int j = 0; j < n - pass; j++) { // the last `pass` items are already in place
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
}
}Source: SimpleSorts.java.
The full pass-by-pass trace from the program:
start [5, 1, 4, 2, 8]
pass 1 (3 swaps) [1, 4, 2, 5, 8]
pass 2 (1 swaps) [1, 2, 4, 5, 8]
pass 3 (0 swaps) [1, 2, 4, 5, 8]
pass 4 (0 swaps) [1, 2, 4, 5, 8]
comparisons=10 swaps=4Source: SimpleSorts.java.
Notice that passes 3 and 4 do no swaps: the array was already sorted after pass 2, yet plain bubble sort keeps going. That is what the early-exit version fixes.
Bubble sort with early exit
If a whole pass makes no swap, the array is sorted. Track that with a boolean and stop.
static int bubbleSortEarlyExit(int[] a) {
int n = a.length, passes = 0;
boolean swapped = true;
for (int pass = 1; pass < n && swapped; pass++) {
swapped = false;
passes++;
for (int j = 0; j < n - pass; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swapped = true;
}
}
}
return passes; // a pass with no swap means: sorted, stop
}already sorted [1, 2, 3, 4, 5, 6, 7, 8]: 1 pass (plain bubble sort always makes 7)
one swap away [1, 2, 4, 3, 5, 6, 7, 8]: 2 passes
reversed [8, 7, 6, 5, 4, 3, 2, 1]: 7 passesOn already sorted input the early-exit version stops after one pass; on a reversed array it still needs every pass. Source: SimpleSorts.java.
Selection sort
Each pass finds the position of the smallest remaining value and swaps it into place. It makes at most one swap per pass, which is why it is the sort to remember when writes are expensive.
static void selectionSort(int[] 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] < a[min]) min = j; // remember where the smallest remaining item is
}
int t = a[i]; a[i] = a[min]; a[min] = t; // one swap per pass
}
}start [5, 1, 4, 2, 8]
pass 1 (min=1 at index 1) [1, 5, 4, 2, 8]
pass 2 (min=2 at index 3) [1, 2, 4, 5, 8]
pass 3 (min=4 at index 2) [1, 2, 4, 5, 8]
pass 4 (min=5 at index 3) [1, 2, 4, 5, 8]
comparisons=10 swaps=4Source: SimpleSorts.java.
The trace shows 4 swaps for 5 elements; two of them (passes 3 and 4) swap an element with itself because it was already in place.
Insertion sort
Treat the left part as sorted. Take the next value (the key), shift larger values one place right, and drop the key into the gap. This is how most people sort a hand of playing cards.
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift larger items one place right
a[j + 1] = a[j];
j--;
}
a[j + 1] = key; // drop the key into the gap
}
}start [5, 1, 4, 2, 8]
insert 1 (1 shifts) [1, 5, 4, 2, 8]
insert 4 (1 shifts) [1, 4, 5, 2, 8]
insert 2 (2 shifts) [1, 2, 4, 5, 8]
insert 8 (0 shifts) [1, 2, 4, 5, 8]
comparisons=7 shifts=4Source: SimpleSorts.java.
Because it stops shifting as soon as it meets a smaller value, insertion sort is fast on nearly sorted data, which the counts below show.
Counting the work on 1,000 elements
The table below lists comparisons / swaps (or shifts for insertion sort). The raw program output follows it.
| Algorithm | Sorted input | Random input | Reversed input |
|---|---|---|---|
| bubble | 499,500 / 0 | 499,500 / 244,720 | 499,500 / 499,500 |
| bubble+exit | 999 / 0 | 498,275 / 244,720 | 499,500 / 499,500 |
| selection | 499,500 / 0 | 499,500 / 994 | 499,500 / 500 |
| insertion | 999 / 0 | 245,712 / 244,720 | 499,500 / 499,500 |
algorithm input comparisons swaps/shifts
bubble sorted 499500 0
bubble random 499500 244720
bubble reversed 499500 499500
bubble+exit sorted 999 0
bubble+exit random 498275 244720
bubble+exit reversed 499500 499500
selection sorted 499500 0
selection random 499500 994
selection reversed 499500 500
insertion sorted 999 0
insertion random 245712 244720
insertion reversed 499500 499500Source: SimpleSorts.java.
Read it like this. Selection sort does 499,500 comparisons whatever the input, but only 994 swaps on random data. Bubble sort without early exit also does 499,500 comparisons even on sorted input; with early exit that drops to 999. Insertion sort needs 999 comparisons on sorted data and 499,500 on reversed.
Stability: why equal keys matter
A sort is stable if equal keys keep their original relative order. This matters when you sort by one column and want an earlier sort by another column to survive. Here Asha and Bala both have 80 marks and Asha comes first in the input.
static void selectionSortItems(Item[] 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].marks() < a[min].marks()) min = j;
Item t = a[i]; a[i] = a[min]; a[min] = t;
}
}
static void insertionSortItems(Item[] a) {
for (int i = 1; i < a.length; i++) {
Item key = a[i];
int j = i - 1;
while (j >= 0 && a[j].marks() > key.marks()) { a[j + 1] = a[j]; j--; }
a[j + 1] = key;
}
}input : [Item[name=Asha, marks=80], Item[name=Bala, marks=80], Item[name=Chitra, marks=60]]
selection : [Item[name=Chitra, marks=60], Item[name=Bala, marks=80], Item[name=Asha, marks=80]]
insertion : [Item[name=Chitra, marks=60], Item[name=Asha, marks=80], Item[name=Bala, marks=80]]
All three match Arrays.sort on 1000 random values: trueSource: SimpleSorts.java.
Insertion sort keeps Asha before Bala. Selection sort swaps Chitra into position 0 by swapping with Asha, which throws Asha past Bala, and the order flips. See Comparable vs Comparator for how Java’s own sorts use this.
Which one to use
In production, none of them.Arrays.sortandList.sortare faster for large inputs. Compare with merge sort and quicksort, both O(n log n) on average. Learn these three because they build the intuition for the faster ones, and because interviews ask for them.
Common interview questions
Which simple sort is best for nearly sorted data?
Insertion sort: O(n) when the array is already sorted, as the 999-comparison row above shows.
Is bubble sort stable?
Yes, as long as the swap condition is strict (>, not >=).
Why is selection sort not stable?
It swaps the minimum into position, which can jump an element past an equal one. The Asha/Bala example shows this.
What is the time complexity of bubble sort with early exit?
O(n) best case (already sorted), O(n²) average and worst.
Which sort does the fewest swaps?
Selection sort: at most n−1.
Common mistakes
- Using
>=in bubble sort, which swaps equal elements and breaks stability. - Running the inner loop to
nevery pass instead ofn − pass, which compares already placed elements and risks an index error ata[j + 1]. - Starting insertion sort at index 0. The first element is a sorted list of one; start at 1.
- Forgetting the early-exit flag reset at the start of each pass.
- Calling these “efficient” sorts. They are O(n²) on average.
FAQ
What is the difference between bubble, selection and insertion sort?
Bubble swaps adjacent pairs, selection picks the minimum and swaps it into place, insertion shifts larger elements to make room for each new value.
What is the time complexity of bubble sort?
O(n²) average and worst; O(n) best with an early-exit flag.
Is insertion sort better than bubble sort?
Usually yes: on random data both do about n²/4 swaps or shifts, but insertion sort does far fewer comparisons (245,712 versus 499,500 in the run above).
Which sorting algorithm does Java use?
Arrays.sort on primitives uses a dual-pivot quicksort, and on objects a stable merge-based sort (TimSort).
No Comments yet!