Size:15

Overview & Concept

Cycle Sort is an in-place, unstable sorting algorithm that is theoretically optimal in terms of memory writes: it minimizes the total number of writes to the original array, performing at most n - 1 writes in the worst case. It operates by decomposing the array permutation into disjoint cyclic orbits and rotating each cycle into place.

How It Works

Cyclic Decomposition: Any permutation of elements can be decomposed into disjoint cyclic paths.

Rank Counting: Computes the correct target index of an item by counting how many elements in the array are strictly smaller.

Direct Displacement: Places the item directly into its calculated target position, taking the displaced element into hand.

Cycle Closure: Continues displacing elements along the cyclic path until returning to the cycle leader.

Step-by-Step Execution

1. Select Cycle LeaderSet cycleStart from 0 to n - 2; hold item = A[cycleStart].

2. Find Destination PositionCount elements smaller than item in A[cycleStart + 1..n - 1] to determine pos.

3. Skip DuplicatesIf A[pos] == item, increment pos to handle duplicates.

4. Swap & Complete OrbitSwap item into A[pos] and continue cycling until pos == cycleStart.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(n²)	O(n²)	O(n²)	O(1)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure cycleSort(A):
  for cycleStart = 0 to n - 2:
    item = A[cycleStart]
    pos = cycleStart + count(x in A[cycleStart+1..] < item)
    if pos == cycleStart: continue
    while item == A[pos]: pos = pos + 1
    swap(item, A[pos])
    while pos != cycleStart:
      pos = cycleStart + count(x in A[cycleStart+1..] < item)
      while item == A[pos]: pos = pos + 1
      swap(item, A[pos])
  return A

Algorithmic Invariants

Write Optimality Invariant: Each element is written to its final destination memory slot at most once.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Optimal memory writes: at most n - 1 writes in the worst case, and 0 writes on sorted data.
•In-place sort requiring O(1) auxiliary space.
•Ideal for systems with high write costs (flash memory, EEPROM).

Trade-offs & Limitations

•O(n²) time complexity in all cases (requires O(n²) comparisons to compute ranks).
•Unstable: equal keys can be displaced non-sequentially.

Real-World Applications

Flash Memory & Solid State Writes

Storage media where write cycles cause physical wear and degrade cell longevity.

EEPROM Microcontrollers

Embedded systems with hard limits on write endurance.

Decision Guide: When to Use

Ideal Scenarios

✓When memory write operations are extremely expensive or physically degrade the storage medium.

Consider Alternatives When

✕When comparison time dominates or when stable sorting is required.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Selection Sort Pigeonhole Sort Counting Sort