Sonith ManakkatSorting is one of the oldest jobs in computing: put names in alphabetical order, prices from low to high, messages newest first. It is also the best way to meet the central idea of algorithms: there are many ways to do the same job, and they differ enormously in how much work they need. This part shows four classic sorts as animated bars. Each section has a plain picture and an Expert view with the precise costs. If you prefer no motion, every animation has a text version of its steps underneath.
The job, and why it matters
Expert viewWhat "sorted" and "cost" mean
Sorting orders items by a key under some comparison rule. Algorithms are compared by how many basic steps they need as the list grows to length n, written in Big-O notation (part 1). Comparison-based sorts (all four here) cannot beat about n log n comparisons in the worst case; that is a proven lower bound for sorting by comparing items. Beyond speed, two properties matter: stability (items with equal keys keep their original order) and extra memory (whether the method needs a second array).
Bubble sort: swap neighbours
Show the 17 steps as text
- Start: bars in a jumbled order.
- 5 is bigger than 2: swap, so the bigger bar moves right.
- 5 and 8 are in order: leave them.
- 8 is bigger than 3: swap, so the bigger bar moves right.
- 8 is bigger than 1: swap, so the bigger bar moves right.
- 8 is bigger than 6: swap, so the bigger bar moves right.
- 2 and 5 are in order: leave them.
- 5 is bigger than 3: swap, so the bigger bar moves right.
- 5 is bigger than 1: swap, so the bigger bar moves right.
- 5 and 6 are in order: leave them.
- 2 and 3 are in order: leave them.
- 3 is bigger than 1: swap, so the bigger bar moves right.
- 3 and 5 are in order: leave them.
- 2 is bigger than 1: swap, so the bigger bar moves right.
- 2 and 3 are in order: leave them.
- 1 and 2 are in order: leave them.
- Sorted: every bar is in place.
Expert viewBubble sort in numbers
Pseudo-code: repeat n-1 passes; in each pass compare each adjacent pair and swap if out of order; each pass fixes one more element at the end. Worst and average case take about n squared / 2 comparisons, so time is O(n squared); best case O(n) if you stop when a pass makes no swaps. Extra memory is O(1) and it is stable. It is rarely used in practice because other simple methods do the same job with fewer operations; its value is teaching.
Insertion sort: build a sorted hand
Show the 7 steps as text
- Start: treat the first bar as a sorted hand of one.
- Take 2: slide the bigger bars right and drop it in place.
- Take 8: it is already bigger than everything before it.
- Take 3: slide the bigger bars right and drop it in place.
- Take 1: slide the bigger bars right and drop it in place.
- Take 6: slide the bigger bars right and drop it in place.
- Sorted: the hand now holds every bar in order.
Expert viewWhy insertion sort still matters
Time is O(n squared) in the worst and average cases, but O(n) when the data is already nearly sorted, because each new item moves only a short way. It is stable, in place (O(1) extra memory) and has very little overhead. That makes it a good choice for small lists and for finishing off nearly sorted data, and many practical sorting routines are known to switch to an insertion-style step for small pieces. I am describing the general idea here and not asserting what any particular library does.
Merge sort: split, then merge
Show the 9 steps as text
- Start: split the row in halves again and again until single bars.
- Merge positions 1 to 2: two sorted halves become one sorted run.
- Merge positions 3 to 4: two sorted halves become one sorted run.
- Merge positions 1 to 4: two sorted halves become one sorted run.
- Merge positions 5 to 6: two sorted halves become one sorted run.
- Merge positions 7 to 8: two sorted halves become one sorted run.
- Merge positions 5 to 8: two sorted halves become one sorted run.
- Merge positions 1 to 8: two sorted halves become one sorted run.
- Sorted: the last merge joined the two big halves.
Expert viewDivide and conquer in practice
Merge sort splits the list into halves (log n levels) and merges at each level in linear time, giving O(n log n) in the best, average and worst cases. Merging needs a temporary array, so extra space is O(n). It is stable when ties are taken from the left half first, and its predictable running time makes it a common choice for sorting records and for sorting data too large for memory (external sorting merges sorted chunks from disk).
Quick sort: pick a pivot
Show the 7 steps as text
- Start: pick the last bar of a range as the pivot.
- Pivot 4: smaller bars go left, bigger go right, and 4 lands in its final place.
- Pivot 1: smaller bars go left, bigger go right, and 1 lands in its final place.
- Pivot 2: smaller bars go left, bigger go right, and 2 lands in its final place.
- Pivot 5: smaller bars go left, bigger go right, and 5 lands in its final place.
- Pivot 8: smaller bars go left, bigger go right, and 8 lands in its final place.
- Sorted: every bar was a pivot or left alone.
Expert viewPivots and worst cases
Quick sort averages O(n log n) with small constant factors and sorts in place (about O(log n) stack space), which is why it is fast in practice. Its worst case is O(n squared), which happens with consistently bad pivots (for example always taking the last item of an already sorted list). Common defences are choosing a pivot at random, taking the median of a few items, or switching strategy if recursion goes too deep. The usual in-place versions are not stable.
Side by side
| Method | Typical time | Worst time | Extra memory | Stable? |
|---|---|---|---|---|
| Bubble sort | O(n squared) | O(n squared) | O(1) | Yes |
| Insertion sort | O(n squared), O(n) if nearly sorted | O(n squared) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n squared) | about O(log n) | Usually no |
- 1,000,000steps for the simple sorts (n squared)
- 10,000steps for merge or quick sort (n log n)
Stability, in plain words
Stable sort
- Equal items keep the order they had before
- Ann (30) stays ahead of Raj (30)
Not stable
- Equal items may swap places
- Raj (30) might end up ahead of Ann (30)
Expert viewWhen stability matters
If you sort a table by one column and then by another, a stable sort preserves the first ordering among ties, which is how multi-key sorting is often built. If you need stability but have an unstable method, you can add the original position as a tie-breaker key.
Which should you use?
- Learning the ideaBubble or insertion sort: simple to follow
- Tiny or nearly sorted listsInsertion sort is quick and has almost no overhead
- Big lists, steady speed, recordsMerge sort: predictable, stable, needs extra memory
- Big lists in memoryQuick sort ideas: fast on average, in place
Try it by hand
- Deal six cards face upIn a jumbled row
- Bubble: swap neighboursCount how many swaps you make
- Deal again: insertionSlide each card into place in your left hand
- Deal again: mergeSplit into pairs, then merge pairs of pairs
- CompareWhich method took the fewest moves for you?
Different methods, same result: the difference is how much work they do.
Frequently asked questions
Why learn sorting algorithms if libraries already sort?
They teach how to reason about cost, trade-offs and design, which applies far beyond sorting.
Which sort is fastest?
It depends on the data and the limits. Quick sort ideas are fast on average, merge sort is steady, insertion sort wins on tiny or nearly sorted lists.
Can anything beat n log n?
Not by comparing items alone. Special methods (such as counting items by value) can be faster when keys are small whole numbers, but they use different tricks.