Replay seven classic sorting algorithms step by step as a bar chart, showing which elements of the array each one compares and which it overwrites. Change the number of items and the initial order (random, nearly sorted, reversed or many duplicates) to see how the comparison and write counts change. It also helps you practice tracing sorting programs line by line, as required in IT certification exams such as Japan's Fundamental Information Technology Engineer Examination.
Favorites and recently used calculators are stored only in this browser (localStorage).
Sorting in action
Comparisons
–
Writes
–
Step
–
Comparing Writing Final position
Comparison on the same data
These are the counts when the same data as above is sorted by each of the seven algorithms. Which one wins depends on the number of items and the initial order.
Algorithm
Comparisons
Writes
Complexity (average / worst)
Stable
A swap counts as two writes. Quicksort uses the last element as the pivot (Lomuto partition scheme), and shell sort uses the gap sequence 1, 4, 13, 40, …; counts vary with the implementation. When there are 20 items or fewer, the values are shown below the bars.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
The basics of comparison sorting: three O(n²) algorithms
Bubble sort repeatedly compares neighboring elements and moves the larger one toward the end, so each pass fixes the largest remaining value at the end. Selection sort finds the minimum of the remaining elements and swaps it to the front, so it always makes n(n−1)/2 comparisons but at most n−1 swaps. Insertion sort inserts each next value into its correct place in the already sorted part, so on nearly sorted data it needs only about n comparisons. All three take O(n²) time on average and slow down sharply as the data grows. Set the number of items to 64 and switch between “Random” and “Nearly sorted”: the comparison counts of insertion sort and of bubble sort (which stops once a pass makes no swaps) drop sharply, while selection sort stays at 2016.
Divide and conquer in O(n log n): merge sort and quicksort
Merge sort splits the array in half, sorts each half, and then combines (merges) the two sorted runs by comparing them from the front. There are log₂ n levels of splitting and the work at each level is proportional to n, so it runs in O(n log n) on any data, but it needs extra memory for n elements. Quicksort moves elements smaller than a reference value (the pivot) to the front and larger ones to the back, then partitions each part again. It is O(n log n) on average and fast in practice, but if the data is already sorted and an end element is used as the pivot, the partitions become lopsided and it degrades to O(n²). Choose “Reversed” as the initial order and select quicksort, and you will see the comparison count approach n(n−1)/2. Real libraries guard against this, for example by using the median of three values as the pivot or switching to heapsort when partitions become unbalanced (introsort).
Heapsort and shell sort
Heapsort builds, inside the array, a binary tree (a binary heap) in which every parent is larger than its children, then repeatedly swaps the maximum at the root with the last element and shrinks the heap by one. The children of element i are elements 2i+1 and 2i+2. It is O(n log n) even in the worst case and needs no extra memory, but because it compares elements that are far apart, its cache efficiency is poor. Shell sort performs insertion sort on elements spaced a gap apart and gradually shrinks the gap. Moving distant elements a long way early on reduces the work left for the final ordinary insertion sort.
Stable sorting and how to read complexity
A sort is stable if elements with equal values (keys) stay in their original relative order after sorting. For example, when employees are sorted by department, employees in the same department remain in employee-number order. Bubble sort, insertion sort and merge sort are stable, while selection sort, quicksort, heapsort and shell sort are generally not. Complexities such as O(n²) and O(n log n) describe how the count grows as the number of items n gets large. For n = 1000, n² is one million while n log₂ n is about ten thousand, so for large data an O(n log n) algorithm wins by a wide margin. It is known that no sort based only on comparisons can do better than O(n log n) in the worst case.
Swapping 5 and 3 gives 3, 5, 8, 1, 4; 5 and 8 stay; swapping 8 and 1 gives 3, 5, 1, 8, 4; and swapping 8 and 4 gives 3, 5, 1, 4, 8. One pass carries the maximum value 8 all the way to the end, fixing its position, and the next pass sorts the remaining four elements in the same way. 1, 3, 8, 5, 4 is the array after one pass of selection sort, which swaps the minimum to the front, and 1, 3, 4, 5, 8 is the fully sorted result.
The first step swaps the overall minimum 10 with 29 at the front, giving 10, 29, 14, 37, 13. The second step swaps 13, the minimum from the second element on, with 29 in the second position, giving 10, 13, 14, 37, 29. Selection sort always makes n(n−1)/2 comparisons but at most one swap per step, which can be an advantage when writes are expensive. 10, 14, 29, 37, 13 is the array after insertion sort has inserted two elements, and 10, 14, 13, 29, 37 is the array after two passes of bubble sort.
If the array is already ascending, each element needs only one comparison with its left neighbor, so the 9 elements take 9 comparisons in total. If it is descending, the element taken out i-th is compared with all i elements to its left, giving 1 + 2 + … + 9 = 45. Insertion sort thus varies greatly with the input, O(n) in the best case and O(n²) in the worst, and it is very fast on nearly sorted data. Shell sort exploits this by first running insertion sort on elements a gap apart, and Timsort also uses insertion sort for short runs.
Heapsort builds a binary heap inside the array and repeatedly swaps the maximum at the root with the last element and shrinks the heap, so it runs in O(n log n) even in the worst case and needs only a constant amount of extra memory. Merge sort is also O(n log n) in the worst case, but on an array it needs a work area proportional to n. Quicksort is O(n log n) on average and fast in practice, but depending on the pivot choice and the data it can degrade to O(n²). Note that heapsort compares elements that are far apart, so its cache efficiency is poor, and it is not stable.
A stable sort keeps elements with the same key (here, the score) in their original relative order. B and D, both with 70, stay in the order B, D, and A and C, both with 80, stay in the order A, C, giving B, D, A, C. Bubble sort, insertion sort and merge sort are stable, while selection sort, quicksort and heapsort are generally not. With a stable sort you can sort by several keys, for example sorting by name first and then by score.
AThe data is in random order and the pivot is chosen at random
BThe number of data items is a power of two
CThe data is already sorted and the first element is always used as the pivot
Show answer and explanation
Answer: C. The data is already sorted and the first element is always used as the pivot
Quicksort splits the elements into those smaller and those larger than the pivot, then splits each part again. If the data is already sorted and the first element is always the pivot, the pivot is the minimum every time and each split is lopsided, with zero elements on one side and all the rest on the other, so it makes n(n−1)/2 comparisons (4,950 for n = 100). Choosing the pivot at random or as the median of three values makes a long run of lopsided splits extremely unlikely. The number of items has nothing to do with this.
The comparisons are 1 vs 2, 4 vs 2, 4 vs 3, 4 vs 8, 7 vs 8, 9 vs 8 and 9 vs 10; at that point the first run is empty, so the remaining 10 is output without a comparison. That is 7 comparisons, the maximum m + n − 1 = 7 for merging runs of lengths m and n. A merge looks at each element of the sorted runs only once, so it takes O(m + n), and since merge sort repeats this over log₂ n levels, the whole sort takes O(n log n).
FAQ
Which sorting algorithm is the fastest?
It depends on the data. Quicksort is often fastest on typical data; merge sort or heapsort is the choice if you need an O(n log n) guarantee even in the worst case; and insertion sort suits nearly sorted or small data. The standard libraries of real programming languages use hybrids of these, such as introsort and Timsort.
What do the comparison and write counts represent?
The comparison count is the number of times two elements were compared. The write count is the number of times an array element was overwritten, with a swap counted as two. With data that is expensive to compare (such as long strings), the comparison count dominates the real speed; with storage that is expensive to write (such as flash memory), the write count does.
How is sorting tested in exams?
IT certification exams such as Japan's Fundamental and Applied Information Technology Engineer Examinations often ask you to fill in blanks in a sorting program, give the state of the array at a certain point, or choose the time complexity or stability of an algorithm. Using “Step” in this tool and comparing each change in the array with your own prediction is good tracing practice.
How much do the counts grow when the number of items increases?
For an O(n²) algorithm, doubling the data roughly quadruples the count. For an O(n log n) algorithm, it a little more than doubles. You can check this by setting the number of items to 16, 32 and 64 and looking at the comparison table for the same data.