Cycle Sort

Average time complexity - O(n^2)

Best-Case time complexity - O(n^2)

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(n)

Cycle Sort writes to the array as few times as possible. It starts on the first element and iterates through the array from left to right. It counts the number of items that are greater and then counts the number of items that are smaller than the item at the current index. Using this information, it is able to calculate the exact position in the array at which the element needs to be placed. Once it calculates this, it finds which element is already occupying that spot, and the calculates what its position is (and then writes the first item to the correct spot), then calculates what the position of the element of that item is, and on and on until it is done.

For example, let's say you have array:

4, 1, 5, 2, 3

Cycle sort would start at index 0, which is 4. Then it would calculate the number of items before 4, which is 3. It would calculate the number of items after 4, which is 1. It would then realize that 4 needs to be the fourth item in the sorted array. The item that is currently already there is 2. So it would place the 4 in that spot, then calculate where 2 would go.

4, 1, 5, 4, 3 2

and place it in that spot (which is the second item). The second item is already occupied by a 1, so it would calculate its position to be the first item. Since it has now gotten back to the starting point, the first "cycle" is completed. The array now looks like this:

1, 2, 5, 4, 3

The algorithm now proceeds to start a new cycle at the second item for the second cycle. However, this is already in the correct spot, so then it moves on the the third item, which is a 5. It places this in the fifth spot, then calculates what was previously there (a 3), and places that in the third spot. The third cycle is now complete, and the array is completely sorted.

1, 2, 3, 4, 5

However, the algorithm will keep iterating through until it finishes every cycle (each of which will not actually modify the array). The algorithm only wrote to the array n times.