Cyclic Sort is a specialized in-place sorting pattern for arrays where the values are integers in a known, dense range, typically 1 to n or 0 to n-1. When the input fits that shape, Cyclic Sort sorts the array in O(n) time and O(1) extra space, beating both comparison-based sorts (O(n log n)) and counting-style approaches that need extra arrays.

Cyclic Sort is an interview pattern rather than a general-purpose sorting algorithm. Many problems that ask you to find missing, duplicate, or out-of-place numbers in an array of n integers from 1 to n reduce to a Cyclic Sort plus a single scan.

This chapter covers when the pattern applies, how the cycle-by-cycle placement works, the implementation, and the family of LeetCode problems that all reduce to one or two lines on top of it.

Cyclic Sort works when every value in the array has a clear "home" index. Two common signatures:

Variants exist for arrays of length n containing values from 1 to n + 1 (the missing-positive case), but they all share the same skeleton: a value belongs at a specific index that can be computed from the value itself.

If the values are arbitrary integers or floats with no relation to indices, Cyclic Sort does not apply. Use Quick Sort, Merge Sort, or another general-purpose algorithm instead.

Walk the array left to right. At each index i:

The swap is O(1), and across the entire algorithm the total number of swaps is bounded by n because each swap places at least one element in its correct home, where it stays. Each loop iteration either performs one such swap or advances i, and i advances at most n times. Total work: O(n).

Input: arr = [3, 1, 5, 4, 2] (values 1..5, length 5, 1-indexed).

Index 0 absorbed three swaps before settling. Every other index needed zero. Across the whole array, exactly four swaps happened, one fewer than n, which matches the worst-case bound (n - 1 swaps to fix n positions).

The 1-to-n variant:

Two implementation details:

For the 0-to-n-1 variant, the only change is int home = arr[i];. For the missing-positive case (values 1 to n+1 with one missing), wrap the swap in a range check: if (arr[i] > 0 && arr[i] <= n && arr[i] != arr[arr[i] - 1]).

The outer loop body either advances i (O(1) work, happens at most n times) or performs a swap. Each swap places at least one value into its correct home position, and once a value is at home it stays there. So the total number of swaps across the entire run is at most n - 1. Total work: O(n).

The misleading visual is that the inner re-check looks like a nested loop. It is not. Across all iterations combined, the body runs at most 2n times: at most n swaps plus at most n advances.

The space cost is O(1). All work happens in place via the swap.

Several LeetCode and interview classics reduce to "run Cyclic Sort, then read the answer off the rearranged array in one scan." Each application below is a single pass on top of the sort.

Missing Number (LC 268)

Array of length n contains n distinct integers from 0 to n. Find the missing one.

The sort places value v at index v (for the 0-indexed variant). The first index where arr[j] != j is the missing value. If every index matches, the missing value is n.

Find All Numbers Disappeared in an Array (LC 448)

Array of length n with values from 1 to n, some duplicated. Find the values that never appear.

After Cyclic Sort, scan for indices j where arr[j] != j + 1. Each such j + 1 is a missing value.

Find All Duplicates in an Array (LC 442)

Same array shape as LC 448, but report the duplicates instead. The duplicates are exactly the values that landed at the wrong index after Cyclic Sort. Scan and report arr[j] for each j where arr[j] != j + 1.

Find the Duplicate Number (LC 287)

Array of length n + 1 with values 1 to n, one duplicated. The duplicate is whatever value remains at index i after the loop cannot place it.

One caveat on LC 287: the problem statement disallows mutating the input, which rules out Cyclic Sort. Floyd's tortoise-and-hare cycle detection solves it without mutation. If mutation is allowed, Cyclic Sort solves it in one pass.

First Missing Positive (LC 41)

Array of arbitrary integers, length n. Find the smallest positive integer that does not appear.

This is the hardest variant of the pattern. Values outside [1, n] are ignored during the swap. After sorting, the first index j where arr[j] != j + 1 gives the answer j + 1. If every index matches, the answer is n + 1.

The range check arr[i] > 0 && arr[i] <= n is the only addition. Negative values, zero, and values larger than n are skipped because they have no valid home in a length-n array.

Set Mismatch (LC 645)

Array of length n with values 1 to n where one value is duplicated and one is missing. After Cyclic Sort, the index where arr[j] != j + 1 gives both answers: the duplicated value is arr[j], and the missing value is j + 1.

For arrays of the right shape (values 1 to n or 0 to n-1), Cyclic Sort dominates every alternative on the two metrics that matter together: time and space.

The sign-flipping trick deserves a special mention. It uses the sign of arr[arr[i] - 1] as a "visited" bit. After processing, indices whose value is still positive correspond to missing values. Sign-flipping is O(n) time and O(1) space like Cyclic Sort, but it scrambles the values; Cyclic Sort produces the sorted array as a useful side effect.

Using i != home instead of arr[i] != arr[home]. The first comparison is index-based and treats two indices holding the same value as if they were different, causing an infinite swap loop on duplicates.

Advancing i after a swap. A productive swap can drop a new out-of-place value at index i. Advancing immediately leaves that value misplaced.

Forgetting the range check in the First Missing Positive variant. Without arr[i] > 0 && arr[i] <= n, negative values cause negative indexing or array-out-of-bounds errors.

Confusing 0-indexed and 1-indexed variants. Mixing arr[i] - 1 and arr[i] in the same loop produces nonsense. Pick one variant for the problem at hand and document it in a comment.

Trying to use Cyclic Sort on arbitrary integers. The algorithm depends on values mapping to indices. Arrays containing arbitrary integers, floats, or strings are not candidates. Confirm the value range matches the index range before applying the pattern.

The algorithm is unstable because the swap step does not respect the original relative order of equal values. For the standard applications this does not matter, as the output is either "the sorted array" or "the list of missing / duplicate values," neither of which depends on stability.