Cycle Sort
Minimizes the number of writes to memory — optimal for write-expensive media.
How it works
Cycle Sort is an in-place comparison sort uniquely designed to minimise the number of writes to the array. It works by decomposing the permutation of unsorted elements into cycles. For each cycle, the algorithm finds the correct destination of the first element, places it there, and continues rotating the cycle until every element in it is at its final sorted position. Each element is written at most once, giving the theoretical minimum of O(n) writes.
The algorithm achieves this write-optimal property at the cost of O(n²) comparisons. For each element it counts how many other elements are smaller to determine its correct rank, a process that touches every remaining element. This makes Cycle Sort impractical for general-purpose sorting compared to O(n log n) algorithms, but uniquely suited to scenarios where writes are orders of magnitude more expensive than reads.
Cycle Sort is in-place with O(1) auxiliary space and not stable — elements are moved directly to their final positions, which can change the relative order of equal values. Its write-optimal guarantee is mathematically proven: any comparison sort requires at least as many writes as Cycle Sort in the worst case, which is exactly n - (number of cycles) writes.
Complexity
Visualizer
Where it's used in the real world
EEPROM / Flash memory programming
Minimises write cycles to extend flash lifespanFlash memory cells wear out after a finite number of program/erase cycles (typically 10k–100k). Sorting data in-place with the minimum possible writes directly extends the storage lifetime. Cycle Sort's guarantee of at most n writes (vs. O(n log n) for quicksort) is significant when sorting lookup tables or calibration data stored in flash.
Write-once media sorting
CD/DVD mastering where writes are expensiveWrite-once optical media cannot be erased. Sorting must be performed in a scratch buffer with minimised write operations before committing. Cycle Sort's minimisation of writes reduces the number of buffer copy operations needed during the mastering pass.
Database page updates on write-heavy storage
Reducing SSD wear levelling overheadSSDs use wear levelling firmware that tracks page write counts. Sorting rows within a database page before a flush with a write-minimising algorithm reduces the number of page writes, decreasing wear levelling pressure and improving write amplification ratios — particularly important for write-intensive OLAP workloads.
Implementation
function cycleSort(arr: number[]): number[] {
const a = [...arr];
const n = a.length;
for (let cs = 0; cs < n - 1; cs++) {
let item = a[cs];
// Find the correct position for item
let pos = cs;
for (let i = cs + 1; i < n; i++) {
if (a[i] < item) pos++;
}
if (pos === cs) continue; // already in place
// Skip duplicates at destination
while (a[pos] === item) pos++;
// Place item and rotate the cycle
[a[pos], item] = [item, a[pos]];
while (pos !== cs) {
pos = cs;
for (let i = cs + 1; i < n; i++) {
if (a[i] < item) pos++;
}
while (a[pos] === item) pos++;
[a[pos], item] = [item, a[pos]];
}
}
return a;
}
// Usage
console.log(cycleSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]