# Sorting algorithms at a glance: twelve methods visualised

> All twelve sorting methods at a glance, from Bubble, Insertion and Merge Sort to Quick, Heap and Tim Sort, each with visualisation, pseudocode and runtime.

Address: https://marckimmel.de/en/informatik/sortieralgorithmen
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen.md

Bubble, Insertion, Selection, Merge, Quick, Heap, Cocktail, Shellsort, Timsort, Introsort and Radix Sort as a bar animation with pseudocode highlight and step log.

## Topics

- [Bubble Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/bubble-sort.md): Interactive Bubble Sort: bars show every comparison and swap, pseudocode highlights the active line. With runtime in every case, stability and use cases.
- [Insertion Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/insertion-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/selection-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/merge-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/quick-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/heap-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/cocktail-sort.md): Interactive Cocktail Sort (Shaker Sort): Bubble Sort in both directions. Tackles the turtle problem, worst case O(n^2), stable.
- [Shellsort](https://marckimmel.de/en/informatik/sortieralgorithmen/shell-sort.md): Interactive 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.
- [Timsort](https://marckimmel.de/en/informatik/sortieralgorithmen/tim-sort.md): Interactive 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.
- [Introsort](https://marckimmel.de/en/informatik/sortieralgorithmen/intro-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/radix-sort.md): Interactive 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 Sort](https://marckimmel.de/en/informatik/sortieralgorithmen/bogo-sort.md): Interactive 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

| Algorithm | Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | yes |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | 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(n^2) | 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(n^2) | O(n^2) | O(1) | yes |
| Shellsort | O(n log n) | O(n^{4/3}) | O(n^2) | 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 |

## Related

- [Computer science](https://marckimmel.de/en/informatik.md)