Sorting

Comparison sorts, distribution sorts, and hybrids — from the ones worth knowing to the ones actually shipped in standard libraries.

Pages in this Section

• Bubble Sort — Bubble sort repeatedly steps through the list, swapping adjacent out-of-order pairs until a pass makes no swaps. It is the canonical "first sort you learn" — easy to understand, almost…
• Bucket Sort — Bucket sort distributes elements into k buckets by value, sorts each bucket, then concatenates. It runs in O(n+k) average time when elements are roughly uniformly distributed across the…
• Counting Sort — Counting sort is a non-comparison sort for integers in a small range [0, k). It tallies how often each value appears, computes a prefix sum to get final positions, then writes each element…
• Cubesort — Cubesort is a parallel comparison sort that maintains a cube-shaped index of sorted runs and merges them adaptively. It is rarely seen in everyday code; the closest practical Python…
• Heapsort — Heapsort is a comparison sort that uses a binary heap to repeatedly extract the maximum. It runs in O(n log n) time, in place, with O(1) extra space — the only mainstream comparison sort…
• Insertion Sort — Insertion sort builds a sorted prefix one element at a time, shifting each new element back to its correct position. It is fast on small or nearly-sorted inputs and is the inner sort used…
• Mergesort — Mergesort is a divide-and-conquer comparison sort that recursively splits the array in half, sorts each half, then merges them. It guarantees O(n log n) on every input, and is the basis for…
• Quicksort — Quicksort is a divide-and-conquer comparison sort that picks a pivot, partitions the array around it, and recursively sorts the partitions. In practice it is the fastest general-purpose…
• Radix Sort — Radix sort is a non-comparison sort that processes integer keys digit by digit, using a stable bucket sort at each digit. It runs in O(n·k) time where k is the number of digits — linear in…
• Selection Sort — Selection sort repeatedly finds the minimum of the unsorted suffix and swaps it into place. It is O(n²) on every input — never adaptive — but it makes the fewest writes of any O(n²) sort,…
• Shell Sort — Shell sort generalizes insertion sort by sorting elements that are gap positions apart, then shrinking the gap until it reaches 1. By the time gap = 1, the array is nearly sorted and the…
• Timsort — Timsort is a hybrid stable sort derived from mergesort and insertion sort. It is the algorithm behind Python's built-in sorted() and list.sort(), and Java's Arrays.sort on object arrays.
• Tree Sort — Tree sort inserts every element into a binary search tree, then performs an in-order traversal to read them out sorted. Performance hinges entirely on the tree staying balanced — with a…

‹ Algorithms