Cycle Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Cycle Sort

An unstable, in-place comparison sort that is theoretically optimal in terms of the total number of array writes: places every element in its final sorted slot by decomposing the array permutation into cycles.

How it works

Cycle Sort is unique because it minimizes array write operations. In systems where writing to memory is highly expensive (e.g. Flash EEPROM memory where write cycles wear out the hardware), Cycle Sort is highly valued because each element is written **either 0 or 1 time** to its final position. The algorithm decomposes the array's permutation into cyclic shifts:

1. Find correct position: For each index cycleStart, take the element at that index (call it item). Search the rest of the array to count how many elements are smaller than item. This count gives its correct sorted index position, pos.
2. Perform write: If pos matches cycleStart, the element is already in place. Otherwise, swap item with the element at pos. This puts the original item in its final sorted position.
3. Rotate cycle: The swapped-out element is now the new active item. Find its correct position and swap again. Repeat this cyclic routing until we write an element back into the starting index cycleStart, completing the cycle.

Complexity

Interactive visualization

Pseudocode

procedure cycleSort(A):
  n ← length(A)
  
  for cycleStart from 0 to n - 2:
    item ← A[cycleStart]
    pos ← cycleStart
    
    for i from cycleStart + 1 to n - 1:
      if A[i] < item:
        pos ← pos + 1
        
    if pos == cycleStart:
      continue
      
    while item == A[pos]:
      pos ← pos + 1
      
    swap item, A[pos]  # item now holds the displaced value
    
    while pos ≠ cycleStart:
      pos ← cycleStart
      for i from cycleStart + 1 to n - 1:
        if A[i] < item:
          pos ← pos + 1
          
      while item == A[pos]:
        pos ← pos + 1
        
      swap item, A[pos]

JavaScript implementation

function cycleSort(arr) {
  const n = arr.length;
  
  for (let cycleStart = 0; cycleStart < n - 1; cycleStart++) {
    let item = arr[cycleStart];
    let pos = cycleStart;
    
    for (let i = cycleStart + 1; i < n; i++) {
      if (arr[i] < item) pos++;
    }
    
    if (pos === cycleStart) continue;
    
    while (item === arr[pos]) pos++;
    
    if (pos !== cycleStart) {
      let temp = arr[pos];
      arr[pos] = item;
      item = temp;
    }
    
    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]) {
        let temp = arr[pos];
        arr[pos] = item;
        item = temp;
      }
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Flash/EEPROM storage: Highly recommended when writing to memory introduces wear or high latency, such as in embedded EEPROM devices.
• Standard computer systems: Avoid Cycle Sort. On general systems, Quicksort, Heapsort, or Mergesort are significantly faster because they have \(O(n \log n)\) time complexity.