Let's look at the code we've been building toward:

for (let i = 0; i < n; i++) {

  while (nums[i] !== i + 1) {

    const home = nums[i] - 1;

    [nums[i], nums[home]] = [nums[home], nums[i]];

  }

}

A while loop nested inside a for loop. Your complexity alarm should be screaming O(n^2). And honestly? That instinct is well-trained. Most nested loops are quadratic. Compare it to a genuinely quadratic sort:

// Bubble sort — truly O(n^2)

for (let i = 0; i < n; i++) {

  for (let j = 0; j < n - i - 1; j++) {

    if (arr[j] > arr[j + 1]) {

      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

    }

  }

}

In bubble sort, the inner loop runs up to n times per outer iteration, regardless of what happened before. That's n * n work in the worst case — genuinely quadratic. But our cyclic sort loop looks different. The inner while doesn't restart fresh each time — it only runs when the current element isn't home. What if each element could only be swapped once across the entire algorithm? Then the total work wouldn't be n * n — it would be n * 1. That's the key question: does each element move at most once?

Here's the proof, and it's surprisingly simple. Think of it as a budget:

// The swap budget:

// - We start with n elements, none at home.

// - Each swap places EXACTLY one element at its home (permanently).

// - Once an element is home, it's never touched again.

// - Therefore: at most n - 1 swaps total.

//   (The last element in every cycle lands for free.)

//

// for (let i = 0; i < n; i++) {       // n iterations

//   while (nums[i] !== i + 1) {       // borrows from shared budget

//     const home = nums[i] - 1;

//     [nums[i], nums[home]] = [nums[home], nums[i]];

//     // ^^^ one swap = one element permanently placed

//   }

// }

The outer for loop visits each index once — that's n iterations. The inner while loop does swaps, but each swap permanently places one element. Once an element reaches its home, it never moves again. So the inner loop isn't doing n work per iteration — it's borrowing from a shared budget of at most n - 1 swaps across the entire algorithm. Why n - 1 and not n? Because the last element in every cycle lands for free — when every other member of the cycle is home, the last one is already sitting in its correct position.

This is amortized analysis: the inner loop looks expensive on any single iteration, but its total cost across all iterations is bounded. The algorithm is O(n) — linear time, linear swaps, no comparisons needed.

At least, when every value is unique. What happens when values repeat?