Nearly sorted input
Insertion sort
Compare Nearly sorted with Minimum at the end. Insertion sort handles both with little work. In bubble sort, a minimum at the far right moves left only one position per pass, despite early exit.
Sorting
Sorting puts elements in order by a chosen key: numbers by value, products by price, or records by date. The elements are preserved; only their order changes.
We will start with three prices and learn a few ways to put them in order. Then we will explore methods that work on whole groups of items, compare their behavior, and see how to choose between them.
A first example
Suppose three items cost 30, 10 and 20. We want to arrange them from cheapest to most expensive.
Before
- 30
- 10
- 20
After
- 10
- 20
- 30
An array is a sequence of items. The sorting key is the value we use to order them: here, the price. We move each whole item, not just its price. N is the number of items in the array; in this example, N = 3.
A comparison asks which of two prices is smaller. A move puts an item in another place; swapping two items writes to two array positions. The players below count comparisons and writes separately.
Start by following the diagram and the explanation of each step. Notice which items are being compared and which have reached their final positions. The code shows the same actions; you can return to it and to the complexity estimates after you understand the idea.
Shared input
Choose one array for all eight sorts. This lets you compare how much work each needs to produce the same result.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Input order affects the work: bubble sort finishes after one pass on sorted input, while reversed input requires more passes.
Bubble sort
The first three methods put the array in order a little at a time. Bubble sort begins with the simplest move: compare two neighbors.
Compare neighbors and swap them when the left value is larger. Each pass moves the largest remaining value to the right.
About this implementation
A pass with no swaps means the array is sorted. Stop immediately.
How much extra space does it need?
Items are rearranged in the original array. Only a few indices and a temporary swap value are needed. Their number does not grow with the array: O(1) extra space.
Does it preserve the order of equal keys?
If item A costs 20 and comes before item B with the same price, A still comes first after sorting. Preserving this order is called stability. It matters when items have other properties besides price.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
If the array is already sorted, one pass is enough to check it. Otherwise, we may need many passes, comparing neighbors again and again. More items can mean both longer passes and more passes.
Best caseO(N)Worst caseO(N²)
A full run can make (N − 1) + (N − 2) + … + 1 = N(N − 1) / 2 comparisons. On sorted input, the first pass makes N − 1 comparisons and stops. Early exit does not make every nearly sorted input cheap: a small item at the far right can move left by only one position per pass.
Selection sort
Bubble sort carries a large value toward the end through neighboring swaps. Selection sort takes a different approach: find the smallest remaining item first, then put it in its final place.
Find the minimum in the remaining part and move it to the front of that part. Repeat for the next position.
About this implementation
There are few swaps, but finding each minimum requires a new scan. Sorted input still needs all comparisons.
How much extra space does it need?
Items are rearranged in the original array. Only a few indices and a temporary swap value are needed. Their number does not grow with the array: O(1) extra space.
Does it preserve the order of equal keys?
Two items priced at 20 may exchange their relative positions. The prices are still correctly sorted, but the original order of equal items is not guaranteed. This is called an unstable sort.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
We must examine all the remaining items to find each minimum, even when they are already in order. The remaining section gets shorter, but we still search it again for every new position.
Best caseO(N²)Worst caseO(N²)
Finding the first minimum takes N − 1 comparisons, the next takes N − 2, and so on. The total is N(N − 1) / 2 for every input order. There are at most N − 1 swaps: few writes do not imply little total work.
Insertion sort
Selection sort searches the remaining items for the next minimum. Insertion sort takes the next item as it comes and finds a place for it among the items already processed.
Keep the left part sorted. Take the next item and move it left until it fits, like inserting a card into your hand.
About this implementation
This version inserts through adjacent swaps. Equal values are not swapped. Nearly sorted input needs little work.
How much extra space does it need?
Items are rearranged in the original array. Only a few indices and a temporary swap value are needed. Their number does not grow with the array: O(1) extra space.
Does it preserve the order of equal keys?
If item A costs 20 and comes before item B with the same price, A still comes first after sorting. Preserving this order is called stability. It matters when items have other properties besides price.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
An item that is already in the right place needs only a quick check. In reverse order, each new item has to move through the entire sorted section. Nearly sorted input usually needs much less moving.
Best caseO(N)Worst caseO(N²)
To make this more precise, call a pair an inversion when the larger item comes before the smaller one. Each adjacent swap removes one inversion. With I inversions, this version takes O(N + I) work. Sorted input has none; reversed distinct keys have N(N − 1) / 2, giving the quadratic worst case.
Merge sort
So far we have placed individual items. Now we will combine whole sections that are already sorted. Since each section is in order, its next smallest item is always at the front.
For example, merging [10, 30] and [20, 40] gives [10, 20, 30, 40]. We choose 10, then 20, then 30, and finally copy the remaining 40. A buffer is a temporary array where we collect that result.
A single-element run is already sorted. Merge adjacent sorted runs of length 1, then 2, 4 and so on. Take the smaller of their next available keys; on a tie, take from the left run.
About this implementation
This is bottom-up merge sort. The temporary buffer appears below the main array. rightStart is the first index of the right run; pairEnd is the last index of the pair. When one run is exhausted, copy the remaining items without further key comparisons. Then copy the buffer back.
How much extra space does it need?
Merging temporarily collects items in a separate buffer before copying them back. The buffer can hold the whole array: twice as many items need twice as much storage. Extra space is O(N).
Does it preserve the order of equal keys?
If item A costs 20 and comes before item B with the same price, A still comes first after sorting. Preserving this order is called stability. It matters when items have other properties besides price.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0
Temporary array
The buffer fills as the algorithm runs.
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
Each pass works through the array, joining short sorted sections into longer ones. Doubling the input size adds just one more merging pass. This version still performs those merges when the input is already sorted.
Best caseO(N log N)Worst caseO(N log N)
Section lengths double: 1, 2, 4, and so on. The number of passes grows like log₂ N, with O(N) work per pass. Together that gives O(N log N) in the best, average and worst cases. Taking from the left section when prices tie preserves the order of equal-price items.
Quicksort
Merge sort combines sorted parts. Quicksort first divides the items into parts: choose a reference value, called the pivot, and separate the smaller values from the rest.
After placing the pivot, the two sides still need sorting. Repeat the same process on each side until a part has at most one item. Having a function solve smaller versions of its own task is called recursion.
Choose the last value as the pivot. Move smaller values left, place the pivot in its final position, then sort the two resulting parts separately.
About this implementation
The call below the function starts quickSort on the whole array. Each nested call has its own firstIndex and lastIndex, both inclusive. This is Lomuto partitioning with the last item as pivot. Average work is O(N log N) for uniformly random permutations of distinct values; sorted input can take O(N²). Space is the worst-case recursion stack.
How much extra space does it need?
No new array is created, but nested quickSort calls keep their range boundaries. In the worst case, call depth grows to N, so the call stack requires O(N) extra space.
Does it preserve the order of equal keys?
Two items priced at 20 may exchange their relative positions. The prices are still correctly sorted, but the original order of equal items is not guaranteed. This is called an unstable sort.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
The pivot decides how evenly the work is divided. Roughly equal parts quickly become small. If each partition leaves one empty side and almost the whole array on the other, we keep scanning a large section.
Best caseO(N log N)Worst caseO(N²)
Partitioning a range takes linear work. Balanced partitions give about log₂ N levels, with O(N) work per level. Repeated splits into sizes 0 and N − 1 instead cost (N − 1) + … + 1 = O(N²). Sorted, reversed, and all-equal inputs produce those poor splits here. Stack space is O(log N) for balanced splits and O(N) in the worst case.
Heap sort
Selection sort repeatedly searches for an extreme value. Heap sort organizes the remaining items so that the largest is always easy to find.
The diagram also draws the array as a tree. The top item is the root. An item with branches leading down to others is their parent; the items below it are its children. These are relationships between array positions, not extra copies of the items.
In a max heap, every parent is at least as large as its children. That puts the largest value at the root, but does not sort the whole array. After moving the maximum to the end, we repair those relationships to find the next maximum.
First build a max heap in the original array. Then move the maximum from the root to the end, shrink the heap, and restore heap order before extracting the next maximum.
About this implementation
The tree and bars show the same items, not two copies in memory. The code shows siftDown in full: choose the child with the larger key and move the parent down until heap order is restored. Building the heap takes O(N); all extractions together take O(N log N) in the worst case. When all keys are equal, every descent stops immediately, giving this implementation an O(N) best case.
How much extra space does it need?
Items are rearranged in the original array. Only a few indices and a temporary swap value are needed. Their number does not grow with the array: O(1) extra space.
Does it preserve the order of equal keys?
Two items priced at 20 may exchange their relative positions. The prices are still correctly sorted, but the original order of equal items is not guaranteed. This is called an unstable sort.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0
Heap · the same items as a tree
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
The heap saves us from searching the entire remaining array for every maximum. After removing one, we repair a single path down the tree. A larger heap makes that path longer, but much more slowly than the number of items grows.
Best caseO(N)Worst caseO(N log N)
Building the heap from the bottom takes O(N): most nodes are close to the leaves and can move only a short distance. Each of the N − 1 extractions may then need O(log N) work to restore heap order. If all keys are equal, each descent stops immediately, so this implementation has an O(N) best case.
Counting sort
The six methods above decide the order by comparing prices. When prices are non-negative integers in a small range, we can instead count how often each price occurs.
For [2, 1, 2], price 1 occurs once and price 2 occurs twice. So the sorted array needs one place for price 1, followed by two places for price 2.
Before
- 2
- 1
- 2
After
- 1
- 2
- 2
Adding the counts as we go gives 1, then 3. These cumulative counts tell us where each price group ends: one item costs at most 1, and all three cost at most 2. We use those boundaries to place the original items in a temporary array, keeping items with equal prices in their original order.
Count how often each price occurs. Cumulative counts give each item a position in a buffer, which is then copied back. The order comes from the prices and their counts.
About this implementation
First scan the array to find its maximum. The table initially stores frequencies, then group boundaries. Place items from right to left while decreasing each boundary to preserve the order of equal items. A large key range needs many empty cells even for a short array.
How much extra space does it need?
A table of K counters and a buffer of N items need O(N + K) extra space. The diagram includes table cells with zero frequencies. This storage is in addition to the input array.
Does it preserve the order of equal keys?
If item A costs 20 and comes before item B with the same price, A still comes first after sorting. Preserving this order is called stability. It matters when items have other properties besides price.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0Table accesses0
Frequency table
Temporary array
The buffer fills as the algorithm runs.
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
Work depends on two sizes: the number of items and the size of the price table. A short array can still need a lot of work if its largest price makes that table huge.
Best caseO(N + K)Worst caseO(N + K)
K is the table size: from 0 through the maximum price, inclusive. Keys must be non-negative integers.
Scanning the input, counting keys, placing items, and copying them back each take O(N) work. Initializing the table and computing cumulative counts take O(K). Together they give O(N + K) time and extra space. Right-to-left placement preserves the order of equal keys. Here K includes unused keys between zero and the maximum.
Radix sort
Counting sort needs a table covering the whole price range. Radix sort looks at one digit at a time, so each pass needs only ten buckets, numbered 0 to 9.
Start with 23, 12, 21 and 13. Collecting them by their ones digit puts them in the order shown below. Then collect by tens, keeping the existing order within each bucket.
Before
- 23
- 12
- 21
- 13
After ones
- 21
- 12
- 23
- 13
After tens
- 12
- 13
- 21
- 23
In the tens bucket for 1, the earlier pass has already put 12 before 13. In the bucket for 2, it has put 21 before 23. Keeping that order lets each pass build on the previous one. Rearranging items inside a bucket could undo that work.
Distribute items by their ones digit, then by their tens digit. After each pass, collect buckets from 0 through 9, keeping the order inside each bucket.
About this implementation
This is LSD radix sort: least significant digit first. The digit being read is highlighted; a one-digit number has a zero tens digit. Keeping bucket order lets the next pass retain the work of the previous one. append adds an item to the end of a bucket.
How much extra space does it need?
Ten buckets together hold N items: O(N + B) extra space, with B = 10. After collection, the buckets are reused for the next digit.
Does it preserve the order of equal keys?
If item A costs 20 and comes before item B with the same price, A still comes first after sorting. Preserving this order is called stability. It matters when items have other properties besides price.
This array is shared by all eight sorts. Changing it resets every example to its first step.
Comparisons0Writes0Digit extractions0
Buckets for the current digit
The buffer fills as the algorithm runs.
Labels A, B… distinguish items with equal prices. Only the number is compared; watch whether the labels keep their order.
Ready for the first step
Complexity
How to read a complexity estimate
A complexity estimate describes how an algorithm’s work grows as the amount of data increases. Here N is the number of items in the array. The best and worst cases show how the input can make the work easier or harder.
Each digit requires another pass through all the items. More items make every pass longer; more digits add passes. With decimal prices, the number of buckets stays at ten.
Best caseO(D · (N + B))Worst caseO(D · (N + B))
D is the number of digits in the maximum value; B = 10 buckets. Examples use positive integers up to 99, so one or two passes are enough.
Each digit pass distributes N items and collects them from B buckets, taking O(N + B) work. Processing D digits gives O(D · (N + B)). Keeping each bucket in insertion order preserves the ordering established by earlier passes. The buckets hold N items in total, so extra space is O(N + B).
One array, different amounts of work
How we count work
Comparisons check two values, including the maximum scan. Writes place an item in the array, buffer or a bucket; a swap makes two writes. Each counts read and write is a separate table access, including zero initialization. Extracting a digit has its own counter. Indices, loop checks and allocation are excluded: this is neither a full instruction count nor elapsed time. A dash means the algorithm does not use that operation.
Complete runs on the input selected above. Animation steps and playback speed are not used to compare algorithms.
| Algorithm | Comparisons | Writes | Table accesses | Digit extractions |
|---|---|---|---|---|
| Bubble sort | — | — | — | — |
| Selection sort | — | — | — | — |
| Insertion sort | — | — | — | — |
| Merge sort | — | — | — | — |
| Quicksort | — | — | — | — |
| Heap sort | — | — | — | — |
| Counting sort | — | — | — | — |
| Radix sort | — | — | — | — |
Comparisons check two values, including the maximum scan. Writes place an item in the array, buffer or a bucket; a swap makes two writes. Each counts read and write is a separate table access, including zero initialization. Extracting a digit has its own counter. Indices, loop checks and allocation are excluded: this is neither a full instruction count nor elapsed time. A dash means the algorithm does not use that operation.
Try sorted input, then reversed input. Bubble sort exits early on the first, while selection sort still checks every remaining value. This quicksort chooses the last item as its pivot, making input order particularly important.
What each sort guarantees
The counters help compare work on the selected array. Choosing a method also means asking what happens to equal items, whether extra storage is needed, and how the work grows on larger inputs.
What stability means for real items
Suppose the input is Potion A (20), Sword (10), Potion B (20), already ordered by arrival time. A stable price sort gives Sword (10), Potion A (20), Potion B (20): the two potions keep their arrival order. An unstable sort may put Potion B before Potion A.
Only the price is the sorting key. The A/B labels identify items; they are not a second sorting key. Choose “Repeated values” to follow the labels, or “All equal” to isolate this behavior. One run that preserves their order does not prove that an algorithm is stable.
Where the items live during sorting
Bubble sort rearranges items in the original array. A swap only needs to hold one item temporarily; a longer array needs no more temporary storage. That is O(1) extra space. Merge sort collects its result in a temporary array: twice as many items need twice as much room, or O(N) extra space.
An algorithm may need extra storage without creating a second array. Quicksort keeps track of unfinished function calls while it processes smaller parts. Those records form the call stack, which also counts toward its memory use.
The properties at a glance
These bounds describe the implementations shown here. They assume constant-time comparisons and moves of fixed-size keys and items. Extra space includes temporary buffers and the call stack, but excludes the input array and the animation.
| Algorithm | Best | Average* | Worst | Extra space† | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(N) | O(N²) | O(N²) | O(1) | Yes |
| Selection sort | O(N²) | O(N²) | O(N²) | O(1) | No |
| Insertion sort | O(N) | O(N²) | O(N²) | O(1) | Yes |
| Merge sort | O(N log N) | O(N log N) | O(N log N) | O(N) | Yes |
| Quicksort | O(N log N) | O(N log N) | O(N²) | O(N) | No |
| Heap sort | O(N) | O(N log N) | O(N log N) | O(1) | No |
| Counting sort | O(N + K) | O(N + K) | O(N + K) | O(N + K) | Yes |
| Radix sort | O(D · (N + B)) | O(D · (N + B)) | O(D · (N + B)) | O(N + B) | Yes |
* For the six comparison sorts, average bounds assume uniformly random permutations of distinct keys. Counting and radix bounds use the stated N, K, D and B regardless of input order. Heap sort’s O(N) best case allows equal keys; with distinct keys, its best case is O(N log N).
† Space bounds are worst-case bounds. In particular, quicksort uses O(N) stack space here; balanced partitions need O(log N).
Choosing a sorting method
Choose based on the data and requirements. The counters above describe one run; complexity describes how work grows.
Many equal values
A stable sort if equal-key order matters
Try merge sort, or counting or radix sort when the keys meet their restrictions. Choose Repeated values or All equal and follow the labels. This last-pivot quicksort makes poor splits on equal keys.
A small range of integer keys
Counting sort
Choose Narrow range. The same N now needs a smaller table. Sparse, very large keys can make that table too costly.
Integers with few digits
Radix sort
Compare the ones and tens passes. Work depends on both the item count and the number of digits.
A worst-case O(N log N) bound
Merge sort or heap sort
Merge preserves equal-item order but uses a buffer. Heap sorts within the array without that guarantee.
In application code, a library sort and its documented guarantees are usually the starting point. These examples help you understand requirements and behavior, not pick a winner by animation speed.
Taking the ideas further
The main ideas are now in place. This section covers the assumptions behind the bounds, the limit on comparison sorting, and techniques used in practical implementations.
Key restrictions and implementation choices
- Bubble sort
- Comparable keys; early exit enabled.
- Selection sort
- Comparable keys; at most N − 1 swaps.
- Insertion sort
- Comparable keys; this version uses adjacent swaps.
- Merge sort
- Comparable keys; bottom-up merging with a buffer.
- Quicksort
- Last-item pivot; average assumes random permutations of distinct keys.
- Heap sort
- Comparable keys; linear best case when all keys are equal.
- Counting sort
- Non-negative integer keys; K = maximum key + 1.
- Radix sort
- Positive integer keys here; D decimal digits, B = 10 buckets.
Implementation details matter: the examples here use bottom-up merge sort and last-pivot Lomuto quicksort.
Why can counting and radix sort beat N log N?
A comparison sort learns the order by comparing keys. For N distinct keys, there are N! possible orders to distinguish. A binary decision tree needs a path of at least log₂(N!) = Θ(N log N) comparisons in the worst case.
Counting and radix sort also use the representation of the keys: table indices or digits. That comparison-only lower bound does not apply. Their advantage has a price: a large range increases K, and longer keys increase D. Neither is a universal linear-time replacement for comparison sorting.
How practical implementations build on these ideas
A random pivot makes quicksort less dependent on the original input order, but does not remove its quadratic worst case. Three-way partitioning separates keys smaller than, equal to, and greater than the pivot, avoiding repeated work on large groups of equal keys.
Hybrid sorts combine useful properties. Introsort switches away from quicksort when partitions become too deep, using heap sort to retain an O(N log N) worst-case bound. TimSort combines sorted runs and insertion sorting with stable merging. For a library sort, check its own documentation for stability, complexity and comparator requirements.