Sorting Algorithms
Bubble, Insertion, Selection, Merge, Quick, Heap, Cocktail, Shellsort, Timsort, Introsort and Radix Sort as a bar animation with pseudocode highlight and step log.
- Bubble SortInteractive Bubble Sort: bars show every comparison and swap, pseudocode highlights the active line. With runtime in every case, stability and use cases.
- Insertion SortInteractive Insertion Sort: builds a sorted prefix on the left and shifts each new element into its slot. Linear best case, quadratic worst case, stable.
- Selection SortInteractive Selection Sort: each round finds the minimum of the unsorted suffix and swaps it to the front. Exactly n-1 writes, always O(n^2), not stable.
- Merge SortInteractive Merge Sort: recursive halving and stable merging with L and R buffers. Guaranteed O(n log n), suited as External Sort for data beyond memory.
- Quick SortInteractive Quick Sort: pick a pivot, partition smaller and larger values, recurse on both halves. Average O(n log n), worst case O(n^2), in-place, not stable.
- Heap SortInteractive Heap Sort with tree view: build a max-heap, swap the root with the last heap element and run siftDown. Guaranteed O(n log n), in-place.
- Cocktail SortInteractive Cocktail Sort (Shaker Sort): Bubble Sort in both directions. Tackles the turtle problem, worst case O(n^2), stable.
- ShellsortInteractive Shellsort: generalised insertion sort that first sorts far-apart pairs and shrinks the gap to 1. Worst case O(n^2) with the standard gap sequence.
- TimsortInteractive Timsort: hybrid of insertion sort for small runs and stable bottom-up merge. Default sort in Python and Java, worst case O(n log n) and stable.
- IntrosortInteractive Introsort: Quick Sort that falls back to Heap Sort when recursion gets too deep and sorts small ranges with Insertion Sort. Guaranteed O(n log n).
- Radix SortInteractive Radix Sort (LSD): stable Counting Sort per digit, base 10 with 10 buckets. Linear O(d · n) for integer keys with a fixed number of digits.
- Bogo SortInteractive Bogo Sort: joke algorithm that Fisher-Yates-shuffles the array until it is sorted by chance. Expected runtime O(n · n!), worst case unbounded.
Comparison of the algorithms
| Bubble Sort | O(n) | O(n2) | O(n2) | O(1) | yes |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n2) | O(n2) | O(1) | yes |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(1) | no |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| Quick Sort | O(n log n) | O(n log n) | O(n2) | O(log n) | no |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | no |
| Cocktail Sort | O(n) | O(n2) | O(n2) | O(1) | yes |
| Shellsort | O(n log n) | O(n4/3) | O(n2) | O(1) | no |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | no |
| Radix Sort | O(d · n) | O(d · n) | O(d · n) | O(n + b) | yes |
| Bogo Sort | O(n) | O(n · n!) | O(∞) | O(1) | no |