TechNoviceTools — SuperSorter

📊 Sorting Algorithms

Eleven algorithms, six families, three languages
High-school level, with the code that runs them.

What Is Sorting — and Why Does It Matter?

Sorting is one of the most studied problems in the entire history of computer science. The reason is simple: searching a sorted list is dramatically faster than searching an unsorted one. If you want to find a contact on your phone, the app finds them almost instantly because the contacts are stored alphabetically. When you search on Google, the results are ranked — sorted for you before the page loaded. Music apps, databases, and every major software system depend on fast sorting running quietly in the background.

This page covers eleven sorting algorithms across six families. Together they span every major design strategy in sorting: swap-based passes, pick-and-place, divide-and-conquer, heap-based extraction, adaptive run merging, and the purely comedic. Unlike the Duck Sorter (six simple algorithms), SuperSorter includes algorithms that are used in production software today.

Big O in plain English

Big O is a way of describing how much work an algorithm does as the size of the input grows. Let n = the number of items being sorted. Then:

  • O(n) — if you double the list, the work doubles. Extremely fast.
  • O(n log n) — a little more than double when you double the list. Most professional sorting algorithms aim for this.
  • O(n²) — if you double the list, the work quadruples. Slow on large data, fine for small arrays.
  • O(n·n!) — expected time for Bogo Sort. Completely impractical for n > 12. Exists only to illustrate how bad an algorithm can be.

SuperSorter covers algorithms from all of these classes — from Bogo Sort’s astronomical O(n·n!) all the way to Timsort’s O(n) best case on nearly-sorted data. Imagining sorting 8 million songs: an O(n log n) algorithm finishes in about a second; an O(n²) algorithm could take over an hour on the same hardware.

⇅ The Bubble / Swap-and-Repeat Family

These algorithms make repeated passes through the list, swapping elements that are in the wrong order. They keep going until a complete pass finds nothing to swap. The key design decision that separates these three algorithms is how big a step to take between comparisons on each pass.

Bubble Sort

The name “bubble sort” comes from the way larger values bubble up to the top (right end) of the list with each pass. It was described formally by American mathematician Edward Friend in 1956 and popularised in CS education throughout the 1960s and 1970s. Today it is famous mainly as the algorithm every CS student learns first — not because it is fast, but because its simplicity makes it the perfect teaching example.

How it works

Walk across the array from left to right. Every time you see two neighbouring elements that are out of order (left bigger than right), swap them. After one full walk, the biggest element has bubbled all the way to the far right — its final position. Walk again, but ignore that last element. Keep going until a full pass makes zero swaps: the array is sorted.

📚 Real-world analogy: Sorting a row of books by height. You keep walking along the shelf, swapping taller books to the right whenever they are next to a shorter neighbour, until the tallest book reaches the end. Repeat with the remaining books.

The early-exit optimisation

If a complete pass makes zero swaps, every pair is already in order and the algorithm exits immediately. On an already-sorted input, this makes the best case O(n) instead of the naive O(n²). Without it, Bubble Sort would waste time on passes that accomplish nothing.

🧠 Key insight: The early-exit flag is what separates a smart Bubble Sort from a naive one. It also exposes Bubble Sort’s main weakness: the “turtle problem” — small values near the right end move leftward only one position per full pass. Cocktail Shaker Sort (below) was invented specifically to fix this.

Complexity: Best O(n)   Average O(n²)   Worst O(n²)   Swaps O(n²)   Stable ✅   Adaptive ✅

Cocktail Shaker Sort (Bidirectional Bubble Sort)

Cocktail Shaker Sort has been independently described many times and goes by several names: Cocktail Sort, Shaker Sort, Bidirectional Bubble Sort, and Ripple Sort. Its origin is hard to pin down because the idea of alternating direction is natural enough that multiple researchers reached it independently. All names share the same core fix: addressing Bubble Sort’s “turtle problem.”

The Turtle Problem

🐢 What is the turtle problem? In plain Bubble Sort, large values near the left end reach the right quickly (one step per comparison per pass). But small values near the right end move leftward only one position per full left-to-right pass. A small value at the far right takes n−1 full passes to reach the left end. These slow-moving small values are called “turtles” because they crawl.

How it works

Alternate direction every pass. The forward pass bubbles the largest remaining value all the way to the right. The backward pass bubbles the smallest remaining value all the way to the left. Both ends lock simultaneously each round. Continue alternating until a full pass in either direction makes zero swaps.

🍸 Real-world analogy: Shaking a jar of marbles — large marbles rise and settle to one end, small marbles sink and settle to the other, with each shake locking more in place at both ends simultaneously.

Complexity: Best O(n)   Average O(n²)   Worst O(n²)   Stable ✅   Adaptive ✅

Comb Sort

Comb Sort was invented by Wlodzimierz Dobosiewicz in 1980 and later popularised by Stephen Lacey and Richard Box in a 1991 Byte Magazine article. It applies the same gap-shrinking insight as Shell Sort, but to Bubble Sort’s swap mechanism rather than Insertion Sort’s shift mechanism. The gap shrink factor of 1.3 was determined empirically and is the value used in virtually every implementation.

How it works

Instead of always comparing adjacent elements (gap = 1), start with a large gap of about n÷1.3. Compare and swap elements gap positions apart across the whole array. Shrink the gap by 1.3 each pass. Once the gap reaches 1, the algorithm becomes Bubble Sort — but on an array that is already nearly sorted thanks to the large-gap passes eliminating turtles early.

🧠 Key insight: The gap-shrinking trick solves the turtle problem in one stroke. A small value near the right end gets compared with an element many positions to its left on the very first pass, jumping it far leftward immediately. By the time gap = 1, turtles are gone and Bubble Sort finishes fast. This is why Comb Sort’s best case is O(n log n) instead of Bubble Sort’s O(n²).

🧹 Real-world analogy: Combing tangled hair. A wide-tooth comb first takes large strokes to untangle big knots quickly. Progressively narrower combs then tackle finer tangles until a fine-tooth comb does the final smooth pass — mostly effortless because the large strokes did the hard work.

Complexity: Best O(n log n)   Average O(n²)   Worst O(n²)   Stable ❌   Adaptive ❌

↑ The Selection & Insertion / Pick-and-Place Family

These algorithms grow a sorted region one element at a time by either picking the minimum from the unsorted region (Selection) or inserting each new element into its correct position in the sorted region (Insertion). Shell Sort extends Insertion Sort with a gap sequence that makes the final pass almost free.

Insertion Sort

Insertion Sort is one of the oldest sorting methods, used by card players for centuries before computers existed. It appeared in the earliest CS literature and is still the algorithm of choice for very small arrays (typically n < 16) inside sophisticated hybrid algorithms like Timsort, which uses it to sort each initial run.

How it works

Maintain a growing sorted region at the left of the array. For each new element, lift it out of the array, then shift sorted elements one position rightward until a gap opens where this element belongs, and drop it in. After processing all elements, the array is sorted.

🃏 Real-world analogy: Sorting a hand of playing cards. You pick up one card at a time and slide it into its correct position among the cards already in your hand. You never swap two cards — you shift cards out of the way to make room, then place the new one.

Why it is adaptive

If the array is nearly sorted, most elements are close to their final positions. Insertion Sort’s inner loop terminates quickly — often after zero or one shift — making it approach O(n) on nearly-sorted data. This is the adaptive behaviour that Timsort and Shell Sort both exploit.

🧠 Key insight: Insertion Sort is the only simple O(n²) algorithm worth using in production. It is the best choice for n < ~16, it sorts online (one element at a time, without needing the whole array in advance), and it is stable. These properties make it indispensable inside larger algorithms.

Complexity: Best O(n)   Average O(n²)   Worst O(n²)   Stable ✅   Adaptive ✅

Selection Sort

Selection Sort is another algorithm with ancient roots — the intuition of “find the smallest item, move it to the front, repeat” predates computers entirely. It appeared in the earliest computing literature alongside Bubble and Insertion Sort and is typically taught as a deliberate contrast to Insertion Sort: same Big O on paper, but very different behaviour in practice.

How it works

Scan the entire unsorted region from beginning to end and find the smallest element. Swap it into the leftmost unsorted position. Shrink the unsorted region by one. Repeat until the array is sorted. Each pass makes exactly one swap, regardless of the data.

Fewest swaps of all six simple algorithms

Selection Sort always makes exactly n−1 swaps — one per pass — no matter what order the data started in. In systems where writing data is expensive (such as flash memory, where each write shortens the storage chip’s life), this guaranteed minimal-write behaviour can matter more than raw speed.

🧍 Real-world analogy: Picking the shortest person from a group to stand at the front of a line, then picking the next shortest from those remaining, and so on. You always have to look at everyone still in the group to be sure you found the shortest.

🧠 Key insight: Selection Sort is not adaptive — it treats a sorted list exactly the same as a random one, always doing the same amount of work. Paradoxically, that predictability can be an advantage in systems programming: knowing exactly how many writes will occur before you start is sometimes more valuable than being fast on easy inputs.

Complexity: Best O(n²)   Average O(n²)   Worst O(n²)   Swaps Always O(n)   Stable ❌   Adaptive ❌

Shell Sort

Shell Sort was invented by Donald Shell (1924–2015) and published in 1959 in Communications of the ACM. It was the first sorting algorithm ever published that broke the O(n²) barrier for average-case performance, launching decades of research into optimal gap sequences. Shell’s original paper is just two pages long but its ideas are still studied today.

How it works

Shell Sort is Insertion Sort with a crucial twist: instead of always comparing elements one position apart, it starts by comparing elements many positions apart. The first gap is n÷2. After one insertion-sort pass with that gap, halve the gap and repeat. When the gap reaches 1, a final standard insertion sort completes the job — but on an array that is already nearly sorted.

Why the final pass is cheap

The large-gap passes are a way of making the array nearly sorted before the gap-1 pass ever runs. Elements far from their correct positions get moved there quickly. The final insertion sort then barely has to work because everything is already close to where it belongs. This is the core insight that makes Shell Sort much faster than plain Insertion Sort.

One pass per gap — exactly

Canonical Shell Sort makes exactly one insertion-sort pass per gap before halving. This is what distinguishes it from the “Shell Hybrid” in SuperSorter’s visualization, which repeats until settled at each gap level. The one-pass-per-gap rule is critical to achieving the better complexity bounds.

🔍 Real-world analogy: Organising a large messy library. Instead of shelving every book in its exact final spot immediately, first sort by rough category (fiction vs. non-fiction), then by first letter of author, then by exact title. Each pass is quick because you work with much smaller decisions; by the time you need to be precise, every section is already nearly right.

🧠 Key insight: Shell Sort and Comb Sort are cousins. Both use large-gap passes that shrink to gap = 1. The difference is in the operation: Comb Sort swaps (like Bubble Sort); Shell Sort does insertion-sort passes (lift and shift). Because Insertion Sort is more efficient than Bubble Sort at the small-gap stage, Shell Sort typically outperforms Comb Sort and is the more studied algorithm.

Complexity: Best O(n log n)   Average O(n log² n)   Worst O(n²)   Stable ❌   Adaptive ❌

÷ Divide and Conquer

These algorithms split the problem in half, solve each half independently, and combine the results. Both guarantee O(n log n) average performance — dramatically better than the O(n²) algorithms — by ensuring that each element only needs to be compared with log n groups of other elements instead of all of them.

Merge Sort

Merge Sort was invented by John von Neumann in 1945 — making it the oldest divide-and-conquer sorting algorithm. It has been continuously used and studied since then and remains one of the most important algorithms in computer science. Its guaranteed O(n log n) worst case and stability make it the standard choice when predictable performance and sort stability both matter.

How it works

Divide the array in half. Recursively sort the left half. Recursively sort the right half. Then merge the two sorted halves into one sorted array. The merge step is the key operation: walk through both sorted halves simultaneously, always picking the smaller of the two front elements, until both halves are exhausted.

🃏 Real-world analogy: Merging two sorted piles of playing cards into one. Hold one pile in each hand. Compare the top cards; take the smaller one and put it face-down on the table. Keep comparing until one pile is empty, then add the rest of the other pile. The result is perfectly sorted.

Guaranteed performance

Unlike QuickSort, Merge Sort’s worst case is always O(n log n). It doesn’t matter if the data is sorted, reverse-sorted, or random — it always divides log n times and merges n elements each time. This predictability is why it is used in external sorting (sorting files too large to fit in RAM) where you cannot afford worst-case quadratic behaviour.

🧠 Key insight: Merge Sort requires O(n) extra memory for the merge buffer — its one significant disadvantage against HeapSort. However, it is stable (equal elements stay in their original order), which is often essential. It is also trivially parallelisable: the two halves can be sorted on different processor cores simultaneously.

Complexity: Best O(n log n)   Average O(n log n)   Worst O(n log n)   Space O(n)   Stable ✅   Adaptive ❌

QuickSort

QuickSort was invented by British computer scientist Tony Hoare in 1959 while he was working on machine translation at Moscow State University. He described it as “my greatest mistake” (because of the null reference, a separate invention) but also as one of his proudest achievements. Despite being invented in the same year as Shell Sort, QuickSort rapidly became the most widely implemented general-purpose sorting algorithm in history.

How it works

Choose a pivot element from the array (we use the middle element). Partition the array so that every element smaller than or equal to the pivot ends up on the left, and every element larger ends up on the right. The pivot is now in its final sorted position. Recursively apply the same process to the left and right sub-arrays.

The pivot choice matters

If you always choose the smallest or largest element as the pivot — for example, always the first element on a sorted input — the partition splits the array into a sub-array of size 0 and one of size n−1, giving O(n²) performance. Choosing the middle element, a random element, or the “median of three” avoids this degenerate case in practice.

🏫 Real-world analogy: Partitioning a class of students by height. Pick a student as the pivot. Ask everyone shorter to stand on the left, everyone taller on the right. The pivot student is now in exactly the right spot. Repeat the same process for the left group and the right group independently.

🧠 Key insight: QuickSort is in-place (uses O(log n) stack space, no large buffer), cache-friendly, and typically faster than Merge Sort in practice due to smaller constant factors. Its O(n²) worst case rarely occurs with good pivot selection. Most language standard libraries (C, C++) use introsort — QuickSort that switches to Heap Sort when recursion depth exceeds a threshold.

Complexity: Best O(n log n)   Average O(n log n)   Worst O(n²)   Space O(log n)   Stable ❌   Adaptive ❌

🏆 Heap-based

Heap Sort uses a binary heap data structure to efficiently find and extract the maximum element repeatedly. It achieves guaranteed O(n log n) with zero extra memory — the only algorithm that combines these two properties.

Heap Sort

Heap Sort was invented by J. W. J. Williams in 1964, who also invented the binary heap data structure it uses. Robert Floyd improved it in the same year with a more efficient heap-construction algorithm, reducing Phase 1 from O(n log n) to O(n). Together, Williams and Floyd gave us the Heap Sort that is still implemented today.

Phase 1 — Build a max-heap

A max-heap is a complete binary tree where every parent is greater than or equal to both its children. Using Floyd’s algorithm, we can build a valid max-heap from an unsorted array in O(n) time by starting from the last non-leaf and working backwards toward the root, calling heapify on each node.

Phase 2 — Extract max repeatedly

The root of a max-heap is always the largest element. Swap the root with the last element in the unsorted region, shrink the heap by one, and restore the heap property. Each extraction costs O(log n). After n−1 extractions, the array is sorted in ascending order in place.

🏆 Real-world analogy: A tournament bracket. First, run a full tournament (build-heap phase) to find the best player. Place the winner in last position. Then re-run the tournament with the remaining players to find the second-best. Keep going until only one player remains in first position.

🧠 Key insight: Heap Sort is the only simple comparison-based algorithm that simultaneously guarantees O(n log n) worst case and O(1) extra space. Merge Sort needs O(n) extra space; QuickSort’s worst case is O(n²). The trade-off is that Heap Sort is not stable and has poor cache behaviour compared to QuickSort in practice, making it less common for general use but ideal as a fallback.

Complexity: Best O(n log n)   Average O(n log n)   Worst O(n log n)   Space O(1)   Stable ❌   Adaptive ❌

✨ Adaptive / Real-world

Adaptive algorithms go beyond just achieving good worst-case complexity — they also exploit existing order in the data to finish faster on partially-sorted inputs. Timsort is the supreme example: the only algorithm here that is simultaneously O(n log n) worst case and deeply adaptive.

Timsort

Timsort was invented by Tim Peters in 2002 for Python and first appeared in Python 2.3. It has since been adopted as the standard sort for Java (since Java 7), Android, and Swift. It is named after its inventor. Timsort is widely regarded as the most sophisticated general-purpose sorting algorithm in practice: no other simple-to-describe algorithm simultaneously achieves O(n) on nearly-sorted data, O(n log n) worst case, and stability.

Phase 1 — Compute minRun and sort chunks

Timsort divides the array into chunks of size minRun, computed so that the number of chunks is close to a power of 2 (which keeps the merge tree balanced). Each chunk is sorted with Insertion Sort — which is optimal for small arrays and can exploit any existing order within the chunk.

Phase 2 — Bottom-up merge, doubling each pass

Adjacent sorted chunks are merged together, doubling the merge width each pass — exactly like the bottom-up iterative Merge Sort in SuperSorter’s visualization. Because each chunk is already sorted, the merges are efficient. The bottom-up approach avoids recursion overhead and ensures the merge tree is balanced.

Why it outperforms everything else on real data

Real-world data is rarely random. Files, databases, and user-generated content tend to have runs — stretches of consecutive elements that are already in sorted or reverse-sorted order. Timsort detects and exploits these natural runs. On truly random data it still achieves O(n log n). On data that is already sorted it achieves O(n). No other common algorithm does both.

🗂 Real-world analogy: Merging pre-sorted filing cabinet drawers. Each drawer is already in alphabetical order. You don’t resort the contents of each drawer — you just merge adjacent drawers by picking the leading folder from whichever drawer is alphabetically first. Each merge step is fast because the source material is already ordered.

🧠 Key insight: Timsort is the only algorithm on this page that is simultaneously O(n log n) worst case and deeply adaptive (approaches O(n) on nearly-sorted data) and stable. These three properties together explain why Python, Java, Android, and Swift all use it. The simplified version here (computeMinRun + insertion-sort chunks + bottom-up merge) captures the two-phase structure faithfully.

Complexity: Best O(n)   Average O(n log n)   Worst O(n log n)   Space O(n)   Stable ✅   Adaptive ✅

🎲 The Absurdist

Not every sorting algorithm was designed to be used. Bogo Sort exists to illustrate what happens when you have no strategy at all — and to give students something to laugh at while they learn why algorithm design matters.

Bogo Sort (Permutation Sort / Stupid Sort)

Bogo Sort has no single inventor — the concept is so obvious and so terrible that it has been independently “invented” many times as a cautionary example. It goes by many names: Permutation Sort, Stupid Sort, Shotgun Sort, Monkey Sort (from the infinite monkey theorem), and Bozo Sort (a related variant). It appears in algorithms textbooks as the archetypal example of an algorithm with no redeeming qualities.

How it works

Check if the array is sorted. If it is, stop. If it is not, randomly shuffle all the elements and check again. Repeat until sorted.

Expected time: O(n · n!)

There are n! possible orderings of n elements. Only one of them is the sorted order. Each shuffle is a uniformly random permutation, so the probability of being sorted after any one shuffle is 1/n!. The expected number of shuffles before a sorted one appears follows a geometric distribution with mean n! — and each shuffle costs O(n) time, giving O(n · n!) expected total work.

For n = 8: 8! = 40,320. Expected shuffles: 40,320. For n = 20: 20! ≈ 2.4 × 1018. Even at a trillion shuffles per second, that would take about 77,000 years.

🃏 Real-world analogy: Dropping a deck of cards, picking them up in a random order, and checking if they are sorted. If not, drop them again. Keep dropping until they land in order. Expected time: approximately until the heat death of the universe for n > 12.

🧠 Key insight: Bogo Sort has a best case of O(n) (if the array happens to already be sorted, one check finds it immediately) and an expected case of O(n · n!). Its worst case is unbounded — in theory you could shuffle forever and never hit the sorted order, though the probability approaches zero. The only legitimate use for Bogo Sort is as a teaching tool to motivate why studying algorithms matters.

Complexity: Best O(n)   Average O(n · n!)   Worst O(∞)   Stable —   Adaptive ❌

☰ All Eleven Algorithms — Side by Side

Use this table to compare all algorithms at a glance. Colour coding: green = fast / efficient, yellow = moderate, red = slow / expensive.

Algorithm Family Best Average Worst Swaps / Moves Stable Adaptive Key idea
Bubble Sort Swap O(n) O(n²) O(n²) O(n²) ✅ ✅ Adjacent swaps; early exit
Cocktail Shaker Swap O(n) O(n²) O(n²) O(n²) ✅ ✅ Bidirectional; fixes turtles
Comb Sort Swap O(n log n) O(n²) O(n²) O(n²) ❌ ❌ Shrinking gap 1.3; kills turtles
Insertion Sort Pick-place O(n) O(n²) O(n²) O(n²) shifts ✅ ✅ Grow sorted left; best for small n
Selection Sort Pick-place O(n²) O(n²) O(n²) O(n) swaps ❌ ❌ Find min each pass; fewest writes
Shell Sort Pick-place O(n log n) O(n log² n) O(n²) O(n²) shifts ❌ ❌ Gapped insertion; coarse-to-fine
Merge Sort Divide O(n log n) O(n log n) O(n log n) O(n) extra ✅ ❌ Divide-and-conquer; guaranteed
QuickSort Divide O(n log n) O(n log n) O(n²) O(log n) stack ❌ ❌ Partition around pivot; in-place
Heap Sort Heap O(n log n) O(n log n) O(n log n) O(1) extra ❌ ❌ Max-heap extract; guaranteed + in-place
Timsort Adaptive O(n) O(n log n) O(n log n) O(n) extra ✅ ✅ minRun + insertion + bottom-up merge
Bogo Sort Absurdist O(n) O(n · n!) O(∞) O(n · n!) — ❌ Shuffle randomly until sorted

✅ What does “Adaptive” mean?

An adaptive algorithm takes advantage of existing order in the data and runs faster when the input is already partially or fully sorted. A non-adaptive algorithm does the same amount of work no matter what order the input is in.

✅ What does “Stable” mean?

A stable sort preserves the original relative order of equal elements. If two elements compare as equal and A came before B in the input, a stable sort guarantees A is still before B in the output. This matters when sorting by multiple fields (e.g., sort by last name, then by first name).

Ready to see them run?

Watch all fifteen sorting algorithms race in the SuperSorter dot-field visualization — set the dot count, choose starting order, and measure elapsed time on real data.

📊 Open SuperSorter →