Introduction to Cyclic Sort Pattern

You are given an array of n numbers, and the values are exactly 1 to n in some order. Sort it.

[3, 1, 5, 4, 2]      becomes      [1, 2, 3, 4, 5]

Any comparison sort will do this in O(N log N). Counting the values into a second array will do it in O(N), at the cost of O(N) extra memory.

Both ignore something the question told you. The values are not arbitrary. They are exactly the numbers 1 to n, and there are exactly n slots to hold them.

So every number already knows where it belongs. The number 1 belongs at index 0, the number `2