1. Cycle start
Try to place the value at each starting position into its final rank.
for (let cycleStart = 0; cycleStart < arr.length - 1; cycleStart++)Typorithm · hard
Cycle Sort
▷ Interactive algorithm labcycle-sortsortingminimum-writesin-placequadratic-time
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Cycle Sort
Sorting Algorithms
Cycle Sort places each value into its final rank while trying to minimize the number of writes.
Cycle Sort is designed for situations where writes are expensive.
For each cycle start, it counts how many values are smaller than the held item.
That count tells the position where the item belongs.
The algorithm writes the item there, then repeats with the displaced item until the cycle closes.
It performs O(n^2) comparisons but can use very few writes.
Preparing algorithm lab…
01
Count smaller values to find final position.
02
Skip if the item is already placed.
03
Handle duplicates by stepping past equals.
04
Close each write cycle before moving on.
05
Optimizes writes, not comparisons.
function cycleSort(arr) {
for (let cycleStart = 0; cycleStart < arr.length - 1; cycleStart++) {
let item = arr[cycleStart];
let position = cycleStart;
for (let i = cycleStart + 1; i < arr.length; i++) {
if (arr[i] < item) position++;
}
if (position === cycleStart) continue;
while (item === arr[position]) position++;
[arr[position], item] = [item, arr[position]];
while (position !== cycleStart) {
position = cycleStart;
for (let i = cycleStart + 1; i < arr.length; i++) {
if (arr[i] < item) position++;
}
while (item === arr[position]) position++;
[arr[position], item] = [item, arr[position]];
}
}
return arr;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Held item
Hold the value that may be written into its correct position.
let item = arr[cycleStart]3. Target position
position counts how many values are smaller than item.
let position = cycleStart4. Count smaller
Every smaller value means item belongs one index farther right.
if (arr[i] < item) position++5. Already placed
Skip writing when the item is already in the correct position.
if (position === cycleStart) continue6. Skip duplicates
Move past equal values so duplicate keys do not overwrite each other.
while (item === arr[position]) position++7. Write item
Place item and hold the value displaced from that position.
[arr[position], item] = [item, arr[position]]8. Close cycle
Keep placing displaced items until the cycle returns to the start.
while (position !== cycleStart)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.