Sorting
Eight ways to put things in orderSorting is everywhere — search results, leaderboards, databases. Watch eight algorithms sort the same array and count their comparisons and swaps. Try the Sorted and Reversed inputs to see each algorithm's best and worst case.
- Simplebubble · selection · insertion — O(n²)
- Fastmerge · quick · heap — O(n log n)
- No comparisonsradix · bucket
- Comparing
- Swap / write
- Pivot / key
- Sorted
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Two words to know: stable and in place
A sort is STABLE if equal values keep their original order (important when sorting records by one field, e.g. students by marks). A sort is IN PLACE if it needs only a few extra variables, not a second array. Merge, radix and bucket sort need extra space; heap and quick sort do not.
// Stable: two students with 90 marks keep their order
// Asha 90, Ravi 75, Meera 90
// → Ravi 75, Asha 90, Meera 90 (stable)
// → Ravi 75, Meera 90, Asha 90 (not stable)
void swap(int *x, int *y) {
int t = *x; *x = *y; *y = t;
}
Bubble · Selection · Insertion
- Bubble: swap wrong-order neighbours; the largest bubbles to the end.
- Selection: find the smallest, swap it to the front.
- Insertion: slide each value left into the sorted part.
- All O(n²) — fine for small arrays.
Merge sort
- Split the array in half, again and again.
- A single value is already sorted.
- Merge two sorted halves by taking the smaller front value.
- Always O(n log n), needs a temp array.
Quick sort
- Pick a pivot (here: the last value).
- Partition: smaller values left, the rest right.
- The pivot is now in its final place.
- Quick sort both sides. Usually the fastest in practice.
Heap sort
- Children of index i are 2i + 1 and 2i + 2.
- Build a max-heap: every parent ≥ its children.
- Swap the root (maximum) to the end; shrink the heap.
- Sift the new root down. O(n log n), in place.
Radix sort
- Put values in 10 buckets by their ones digit.
- Collect buckets 0 → 9, keeping order inside each.
- Repeat for tens, hundreds, …
- No comparisons: O(d · (n + 10)).
Bucket sort
- Split the value range into k buckets.
- Drop each value into its bucket.
- Sort each (small) bucket.
- Join the buckets. O(n + k) for evenly spread values.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of values, d = number of digits, k = number of buckets. The O(n log n) comparison sorts cannot be beaten by any sort that only compares values; radix and bucket sort avoid comparisons.
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Bubble sort | O(n) |
O(n²) |
O(n²) |
Grows with n |
| Selection sort | O(n²) |
O(n²) |
O(n²) |
Grows with n |
| Insertion sort | O(n) |
O(n²) |
O(n²) |
Grows with n |
| Merge sort | O(n log n) |
O(n log n) |
O(n log n) |
Grows with n |
| Quick sort | O(n log n) |
O(n log n) |
O(n²) |
Grows with n |
| Heap sort | O(n log n) |
O(n log n) |
O(n log n) |
Grows with n |
| Radix sort | O(d·(n + 10)) |
O(d·(n + 10)) |
O(d·(n + 10)) |
Grows with n |
| Bucket sort | O(n + k) |
O(n + k) |
O(n²) |
Grows with n |
All eight at a glance
| Algorithm | Stable? | In place? | Extra space | Good for |
|---|---|---|---|---|
| Bubble | Yes | Yes | O(1) | Teaching; detecting an already sorted array |
| Selection | No | Yes | O(1) | When swaps (writes) are expensive |
| Insertion | Yes | Yes | O(1) | Small or nearly sorted arrays |
| Merge | Yes | No | O(n) | Guaranteed O(n log n), linked lists, huge files |
| Quick | No | Yes | O(log n) | Fastest in practice on average |
| Heap | No | Yes | O(1) | O(n log n) worst case with no extra memory |
| Radix | Yes | No | O(n + 10) | Many integers with few digits |
| Bucket | Yes | No | O(n + k) | Values spread evenly over a range |
Best and worst inputs
| Algorithm | Already sorted | Reversed |
|---|---|---|
| Bubble (with early stop) | O(n) — one pass, no swaps | O(n²) — every pair swaps |
| Insertion | O(n) — nothing shifts | O(n²) — everything shifts |
| Selection | O(n²) — still scans everything | O(n²) |
| Quick (last element as pivot) | O(n²) — the pivot is always the max | O(n²) — the pivot is always the min |
| Merge / Heap | O(n log n) | O(n log n) |
Check your understanding
Answer each question — you will see the explanation straight away.
Which sort runs in O(n) on an array that is already sorted?
Each value is compared once with its left neighbour and nothing needs to shift. (Bubble sort with an early stop is also O(n).)
After the first pass of bubble sort, which value is guaranteed to be in its final place?
The largest value keeps winning its comparisons, so it is carried all the way to the last position.
What does quick sort guarantee after one partition?
Everything smaller is on its left and everything else on its right, so the pivot never moves again.
Which of these sorts is NOT stable?
Heap sort swaps values across long distances, so equal values can change their order.
Radix sort on [170, 45, 75, 90]: what order do you get after the ones-digit pass?
Ones digits are 0, 5, 5, 0. Bucket 0 holds 170, 90 and bucket 5 holds 45, 75 — each bucket keeps its order.
Why does merge sort need O(n) extra memory?
While merging, values are written into a temp array (they cannot overwrite values not yet merged), then copied back.
Sorting quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.