Interactive demo
Crumsort Visualization
Crumsort by Igor van den Hoven is a very fast in-place sorting algorithm. Its fulcrum partition takes the pivot out of the array and then keeps filling the gap from both ends, which needs fewer writes than swapping.
Watch the gap: it jumps between the left and the right end. With “Few unique values” you can see that crumsort is not stable.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element
- Pivot (held out of the array)
- ≤ pivot
- > pivot
- Final position
Runtime and properties
Best case
O(n)
Its analyzer recognizes sorted and reversed input with n comparisons.
Average case
O(n log n)
Partitions like quicksort, with fewer writes thanks to the fulcrum partition.
Worst case
O(n log n)
Very unbalanced partitions switch to quadsort, a merge sort.
Extra memory
O(log n)
A fixed buffer of 512 elements plus the recursion stack.
Stable
No
Filling gaps from both ends changes the order of equal elements.
In-place
Yes
The partition only fills gaps within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| 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 this page | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Analyze and choose a pivot
Like fluxsort, crumsort first checks whether the array is sorted or reversed. Then it chooses a pivot, here the median of the first, middle and last element.
2. The fulcrum partition
The pivot is taken out, leaving a gap at the left end. From the right, the first element ≤ pivot moves into that gap, which leaves a gap on the right. From the left, the first element > pivot fills it, and so on, until both ends meet and the pivot fills the last gap.
3. Simplified here
This visualization uses a gap of one element, as in the reference version of the README. The original moves 32 elements to a small swap space to compare them without branches, uses the pseudomedian of 9 and sorts parts below 24 elements with quadsort.
Credits
- Crumsort was created by Igor van den Hoven. The partition on this page follows the reference fulcrum partition from his README, simplified as described above; the original is at github.com/scandum/crumsort.