Sorting Algorithms
Ordering data — the art of compare & swap. Learn the 8 topics below step by step with interactive visualizations.
Sorts by comparing adjacent elements; the larger value is pushed one slot at a time toward the end, which is where the name comes from. Simple to implement, but unsuitable for large data.
O(n²)Compares each element against the already-sorted portion and inserts it into the right position. Remarkably fast when the data is nearly sorted.
O(n²)An intuitive in-place algorithm that repeatedly finds the smallest (or largest) element and swaps it to the front.
O(n²)A generalization of insertion sort that repeats gapped insertion while progressively shrinking the gap, moving distant elements efficiently. Performance hinges on the gap sequence.
O(n log² n)A fast, efficient divide-and-conquer algorithm that sorts by partitioning the array around a pivot. It underlies the built-in sort in most languages.
O(n log n)A stable divide-and-conquer algorithm with consistent performance: split the array until indivisible, then merge back while sorting.
O(n log n)An in-place algorithm that rebuilds the array into a max-heap and repeatedly extracts the root (maximum) to sort. Guarantees O(n log n) even in the worst case.
O(n log n)A non-comparison algorithm that sorts by counting value frequencies. When the value range k is limited, it sorts stably in linear O(n+k) time.
O(n + k)