Interactive demo
Fluxsort Visualization
Fluxsort by Igor van den Hoven is one of the fastest stable sorting algorithms. It partitions like quicksort, but copies the larger elements to swap memory, which keeps equal elements in their order.
Choose “Sorted” or “Reversed”: the analyzer is done after one pass. With “Few unique values” you can see that fluxsort is stable.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element
- Pivot
- ≤ pivot, stays in the array
- > pivot, in swap memory
- Compared pair (small part)
- 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 a carefully chosen pivot.
Worst case
O(n log n)
Very unbalanced partitions switch to quadsort, a merge sort.
Extra memory
O(n)
Swap memory for up to n elements, plus the recursion stack.
Stable
Yes
Elements keep their order when they are copied to swap memory and back.
In-place
No
Larger elements are moved to the swap memory.
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 this page | 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 |
1. Analyze
First, fluxsort checks how ordered the array is. Sorted arrays are done and reversed ones are flipped, both with n comparisons. The original also measures the order of four segments and switches to quadsort, a merge sort, for mostly ordered data.
2. Partition into swap memory
Elements up to the pivot are packed to the front of the array, larger ones are copied to swap memory, both in their original order. That is why fluxsort is stable, unlike quicksort.
3. Simplified here
This visualization uses the median of 3 as pivot instead of the quasimedian of 9, copies the swap memory back before going on, and sorts parts of up to 3 elements directly. The original sorts parts below 96 elements with quadsort and has more safeguards.
Credits
- Fluxsort was created by Igor van den Hoven. This page shows a simplified version based on his description; the original and its documentation are at github.com/scandum/fluxsort.