Interactive demo
Sorting Algorithms
Sixteen sorting algorithms, animated step by step: from simple ones like bubble sort to modern hybrids like fluxsort and crumsort. Every page counts comparisons and writes, so you can see how fast each one really is.
Simple sorting
Bubble sort
Swaps neighbors until the largest elements have bubbled to the end.
- Best case
- O(n)
- Average case
- O(n²)
- Worst case
- O(n²)
Stable: YesIn-place: Yes
Selection sort
Selects the smallest remaining element and swaps it to the front.
- Best case
- O(n²)
- Average case
- O(n²)
- Worst case
- O(n²)
Stable: NoIn-place: Yes
Insertion sort
Inserts one element after the other into a growing sorted part.
- Best case
- O(n)
- Average case
- O(n²)
- Worst case
- O(n²)
Stable: YesIn-place: Yes
Shell sort
Insertion sort over shrinking gaps, so elements first make big jumps.
- Best case
- O(n log n)
- Average case
- ≈ O(n1.25)
- Worst case
- O(n1.5)
Stable: NoIn-place: Yes
Trees and heaps
Tree sort
Builds a binary search tree and reads it in order.
- Best case
- O(n log n)
- Average case
- O(n log n)
- Worst case
- O(n²)
Stable: YesIn-place: No
Tournament sort
Plays a knockout tournament in which the smallest element always wins.
- Best case
- O(n log n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: YesIn-place: No
Heapsort
Builds a max-heap and keeps moving its maximum to the end.
- Best case
- O(n log n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: NoIn-place: Yes
Smoothsort
A heapsort over a forest of Leonardo heaps that adapts to sorted input, by Edsger W. Dijkstra.
- Best case
- O(n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: NoIn-place: Yes
Merging
Merge sort
Divides the array into halves and merges the sorted halves.
- Best case
- O(n log n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: YesIn-place: No
Patience sort
Deals the elements into piles like the card game, then collects the smallest top card.
- Best case
- O(n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: YesIn-place: No
Timsort
Finds the runs that are already in order and merges them cleverly, by Tim Peters.
- Best case
- O(n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: YesIn-place: No
Block sort
A stable merge sort that needs no extra memory, merging by moving whole blocks.
- Best case
- O(n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: YesIn-place: Yes
Partitioning
Quicksort
Partitions around a pivot and sorts both sides recursively.
- Best case
- O(n log n)
- Average case
- O(n log n)
- Worst case
- O(n²)
Stable: NoIn-place: Yes
Introsort
Quicksort that switches to heapsort when the recursion gets too deep, by David Musser.
- Best case
- O(n log n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: NoIn-place: Yes
Fluxsort
A stable quicksort that partitions into swap memory, by Igor van den Hoven.
- Best case
- O(n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: YesIn-place: No
Crumsort
An in-place quicksort with the gap-filling fulcrum partition, by Igor van den Hoven.
- Best case
- O(n)
- Average case
- O(n log n)
- Worst case
- O(n log n)
Stable: NoIn-place: Yes
Compared at a glance
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.