Sorting

Bubble SortsimpleBubble sort repeatedly steps through the list, swapping adjacent out-of-order pairs until a pass makes no… Bucket Sortnon comparisonBucket sort distributes elements into k buckets by value, sorts each bucket, then concatenates. Counting Sortnon comparisonCounting sort is a non-comparison sort for integers in a small range [0, k). CubesortefficientCubesort is a parallel comparison sort that maintains a cube-shaped index of sorted runs and merges them… HeapsortefficientHeapsort is a comparison sort that uses a binary heap to repeatedly extract the maximum. Insertion SortsimpleInsertion sort builds a sorted prefix one element at a time, shifting each new element back to its correct… MergesortefficientMergesort is a divide-and-conquer comparison sort that recursively splits the array in half, sorts each half,… QuicksortefficientQuicksort is a divide-and-conquer comparison sort that picks a pivot, partitions the array around it, and… Radix Sortnon comparisonRadix sort is a non-comparison sort that processes integer keys digit by digit, using a stable bucket sort at… Selection SortsimpleSelection sort repeatedly finds the minimum of the unsorted suffix and swaps it into place. Shell SortsimpleShell sort generalizes insertion sort by sorting elements that are gap positions apart, then shrinking the… TimsortefficientTimsort is a hybrid stable sort derived from mergesort and insertion sort. Tree SortefficientTree sort inserts every element into a binary search tree, then performs an in-order traversal to read them… Efficient SortsSectionO(n log n) comparison sorts: mergesort, quicksort, heapsort, Timsort, tree sort and Cubesort. Non-Comparison SortsSectionSorts that beat O(n log n) by not comparing keys: counting, radix and bucket sort. Simple SortsSectionQuadratic-time comparison sorts that are easy to reason about: bubble, insertion, selection and Shell sort.

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

‹ Algorithms