Cycle Sort

The problem

A common interview setup: you're handed an array holding the numbers 1 to n (or 0 to n-1), shuffled. Sometimes one is missing and a duplicate takes its place, and you must find the culprit. You could reach for quicksort — but a general-purpose sort ignores a gift sitting in plain sight.

The gift is this: you already know exactly where every value belongs. The number 1 goes at index 0, the number 7 goes at index 6. There's no comparing needed — the value is its own address. A sort that exploits this can run in linear time and, remarkably, with the fewest memory writes any sort can possibly make.

A first attempt

Sort it normally in O(n log n), then loop to find which index i doesn't hold i+1. Correct, but wasteful on two fronts: you're doing comparison-based work on data that needs no comparisons, and you're moving elements around far more than necessary.

That "far more than necessary" part matters in the real world. If each write is expensive — think flash memory with limited write cycles, or auditing every mutation — you want to touch each slot as few times as you can. Comparison sorts don't optimize for that at all.

The insight

Because value v belongs at index v-1, misplaced elements form cycles: v is sitting where u should go, u is sitting where w should go, and eventually the chain loops back. If you rotate each cycle once, putting every element home in a single motion, you write each element at most once. That's provably the minimum number of writes possible — you can't place a misplaced element without writing it at least once.

So instead of comparing, you follow the value to its home, evict whatever lives there, and follow that evicted value onward, closing the loop. Sorting becomes navigation.

How it works

For an array of 1..n living at indices 0..n-1, the home of value v is index v - 1.

Sorting [3, 1, 2] (values 1..3, home of v is index v-1):

i=0: hold 3 → home is index 2, swap    [2  1  3]   now holding 2
     hold 2 → home is index 1, swap    [1  2  3]   now holding 1
     hold 1 → home is index 0 = i, stop. cycle closed.
i=1: nums[1]=2 already home, skip
i=2: nums[2]=3 already home, skip → sorted

The code

This variant sorts values 1..n in place. (For 0..n-1, the home index is simply nums[i].)

def cycle_sort(nums):
    i = 0
    while i < len(nums):
        home = nums[i] - 1              # where nums[i] belongs
        if nums[i] != nums[home]:       # not yet in place
            nums[i], nums[home] = nums[home], nums[i]
        else:
            i += 1                      # this slot is settled
    return nums

function cycleSort(nums: number[]): number[] {
  let i = 0;
  while (i < nums.length) {
    const home = nums[i] - 1; // where nums[i] belongs
    if (nums[i] !== nums[home]) {
      [nums[i], nums[home]] = [nums[home], nums[i]];
    } else {
      i++; // this slot is settled
    }
  }
  return nums;
}

void cycleSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int home = nums[i] - 1;          // where nums[i] belongs
        if (nums[i] != nums[home]) {
            int t = nums[i]; nums[i] = nums[home]; nums[home] = t;
        } else {
            i++;                         // this slot is settled
        }
    }
}

void cycle_sort(int *nums, int n) {
    int i = 0;
    while (i < n) {
        int home = nums[i] - 1;          /* where nums[i] belongs */
        if (nums[i] != nums[home]) {
            int t = nums[i]; nums[i] = nums[home]; nums[home] = t;
        } else {
            i++;                         /* this slot is settled */
        }
    }
}

#include <vector>
#include <utility>
using namespace std;

void cycleSort(vector<int> &nums) {
    int i = 0, n = (int)nums.size();
    while (i < n) {
        int home = nums[i] - 1;          // where nums[i] belongs
        if (nums[i] != nums[home]) {
            swap(nums[i], nums[home]);
        } else {
            i++;                         // this slot is settled
        }
    }
}

Complexity

This linear time is possible only because we sort by known position, not by comparison — sidestepping the O(n log n) comparison lower bound from the intro lesson.

When to use it

Practice

Recap

• Cycle sort exploits that value v has a known home index, forming cycles it rotates to place every element in O(n) with the minimum possible writes.
• It only works on values in a dense, index-mappable range like 1..n — not general data.
• It's the go-to for in-place "find the missing / duplicate / misplaced number" problems.