Intermediate · 20 minYou are hereRead
Bubble sort
Swapping neighbours that are out of order carries the largest remaining value to the end on each pass, and a pass with no swaps ends the sort.
Sorting and hashing
Sorting
Lessons on this topic
Intermediate · 20 minYou are hereRead
Insertion sort
Grow a sorted prefix one value at a time by sliding each new value left into its place. Nearly sorted input costs almost nothing.
Intermediate · 15 minYou are hereRead
Selection sort
Find the smallest remaining value and swap it into the next place. It always makes n(n − 1)/2 comparisons, but at most n − 1 swaps.
Intermediate · 20 minYou are hereRead
Shell sort
Insertion sort on values a gap apart, with the gap shrinking to 1, moves small values a long way early and leaves little work for the final pass.
Intermediate · 25 minYou are hereRead
Merge sort
Split the array in half, sort each half the same way, and merge the sorted halves in one pass. At most about n log₂ n comparisons, stable, with n extra cells.
Intermediate · 25 minYou are hereRead
Quicksort
Partition round a pivot so smaller values go left and larger ones right, then sort each side the same way, in place. Fast on average, n(n − 1)/2 comparisons at worst.
Intermediate · 20 minYou are hereRead
Counting sort
When the keys are small integers, count each key, take running totals, and every item knows its final place. O(n + k) steps, with no comparisons at all.
Intermediate · 20 minYou are hereRead
Bucket sort
Values spread evenly over a range drop into n buckets; each bucket holds only a few, so keeping each one sorted is cheap. O(n) on average, O(n²) when the values bunch.
Intermediate · 20 minYou are hereRead
Radix sort
Sort by the last digit with a stable sort, then by the next digit, then by the first, and the numbers are sorted. O(d(n + b)) for d digits in base b.
Related topics