Every other in-place comparison sort on this site treats writes and comparisons as roughly the
same kind of cost — selection sort does O(n)
swaps without a second thought, insertion sort shifts
a whole run of elements one slot to make room for one. Cycle Sort starts from a
different premise: what if writing to memory is the expensive part, and comparing is cheap? It
answers by guaranteeing something none of this site's other nine comparison sorts even attempt —
every element is written to array memory at most once, directly into its final sorted
position, for the entire sort. An element already sitting where it belongs is never touched at
all. That's not an average or a best case; it's the actual minimum number of writes any
comparison-based in-place sort could possibly need, and Cycle Sort hits it exactly, every time.
Enter a comma-separated array (duplicates welcome) and step through. Each outer step picks the next unfinalized index as a cycle start and asks "how many elements belong before this one?" — that count is the correct position. The algorithm then follows the chain of displaced values (the "cycle") until it loops back to where it started. Watch the two counters at the bottom: comparisons climbs on every step, but writes only increments when a value actually needs to move — an already-correct index costs zero writes, not a skipped-but-still-counted one.
Take whatever value sits at some unfinalized index cycleStart and call it
item. Count how many of the other not-yet-finalized elements are smaller than
item — that count is exactly item's correct index once everything is
sorted, because in sorted order an element's position is the number of elements smaller
than it. If that count equals cycleStart already, item is home; move on
with zero writes. Otherwise, write item into its correct position, which evicts
whatever was sitting there — call that next. next now needs a home too,
found the exact same way (count how many elements are smaller than it), and the process repeats:
displace, evict, re-place, until the chain of evictions loops back around to cycleStart
itself. That closed loop is the "cycle" the algorithm is named for. Because every index on a cycle
gets written exactly once — the position-counting step never has to guess or backtrack, it computes
the final answer directly — no element is ever written twice, and no element that's already correct
is written at all.
Duplicates need one extra rule: if several equal values are still unplaced, counting "smaller
than" alone can't tell them apart, and two of them would try to claim the same index. The fix is
to walk forward past any array slot that already holds a value equal to item before
writing — that spreads a run of duplicates across their whole equal-valued block instead of
colliding on its first slot, and it's what keeps the cycle from spinning forever on repeated
values (see Pitfalls below).
function cycleSort(input) {
const arr = input.slice();
const n = arr.length;
let writes = 0;
for (let cycleStart = 0; cycleStart < n - 1; cycleStart++) {
let item = arr[cycleStart];
// Where does item belong? Count elements smaller than it, past cycleStart.
let pos = cycleStart;
for (let i = cycleStart + 1; i < n; i++) {
if (arr[i] < item) pos++;
}
if (pos === cycleStart) continue; // already home — zero writes
while (item === arr[pos]) pos++; // skip past equal duplicates
[arr[pos], item] = [item, arr[pos]]; // place item, carry the evicted value
writes++;
// Follow the cycle: keep placing the carried value until it returns to cycleStart.
while (pos !== cycleStart) {
pos = cycleStart;
for (let i = cycleStart + 1; i < n; i++) {
if (arr[i] < item) pos++;
}
while (item === arr[pos]) pos++;
if (item !== arr[pos]) {
[arr[pos], item] = [item, arr[pos]];
writes++;
}
}
}
return arr; // writes is available for inspection too
}The outer loop only needs to run to n - 2: once every earlier index is finalized,
whatever's left at the last slot has nowhere else to go.
Skipping the duplicate-skip step doesn't just misplace a few values — it hangs the
algorithm outright, most of the time. Remove the while (item === arr[pos])
pos++; line and run on arrays with repeated values (range 0–7, lengths 2–16,
3,000 random trials with a generous iteration cap standing in for an infinite loop): 2,031
of 3,000 trials (67.7%) either came back wrong or never terminated — almost all of those
were hangs, not silently-wrong output. Two equal values both compute the same "count smaller than
me" position, so the cycle keeps trying to write two different carried values into the same slot
and never converges back to cycleStart.
Using <= instead of < when counting smaller elements is
just as broken, for a related reason. That single-character change makes every value
count itself and every one of its own duplicates as "smaller," inflating pos past
where the value actually belongs — often past the end of the array entirely. Same test setup:
2,453 of 3,000 trials (81.8%) came back wrong or hung. The strict
< is load-bearing, not a style choice.
The minimal-writes property is real, not just a name — measured against selection
sort on the same inputs. Selection sort also runs in O(n²) and also
sorts in place, so it's the natural comparison. Across 3,000 random arrays (length
5–29), counting every individual array-slot write (a swap counts as two): Cycle Sort's
writes were never once more than selection sort's on the same input, and
selection sort wrote strictly more in 2,945 of 3,000 trials (98.2%) — on average
27.6 writes for selection sort against 16.1 for Cycle Sort on the same arrays, about 71% more.
That guarantee doesn't make it stable. Cycle Sort can and does reorder equal elements relative to each other — the duplicate-skip rule places same-valued items in the order it happens to encounter them along a cycle, not the order they started in. Checked directly: across 500 trials of length-tagged duplicate-heavy arrays, at least one equal-value pair came back out of original order in every single run where duplicates were present.
Time: O(n²) comparisons, worst case and typical case alike —
finding each element's position requires scanning the remaining unfinalized elements no matter
what order they're in, the same floor selection
sort sits at. Writes: exactly n minus the number of elements
already in their correct position — the provable minimum for any in-place comparison sort, and
strictly fewer than selection sort needs on the same input in the overwhelming majority of cases
(measured above). Space: O(1) auxiliary — everything happens in
place, with only the one carried item variable held outside the array at any moment.
Stable: no (measured above).
Cycle Sort trades away every advantage the rest of this site's comparison sorts compete on — typical-case speed, adaptivity, a fixed schedule — for a single guarantee none of them make: the fewest possible writes to the array. That trade only pays off when writes are the genuinely scarce resource, which for RAM they normally aren't — but for flash memory and EEPROM, where each write wears the medium down and a comparison costs nothing by contrast, it's the entire point.