Summary

Cycle Sort is a comparison-based algorithm designed to minimize the total number of memory writes. It works by decomposing the array into a set of "cycles". For each element, the algorithm calculates its correct final position by counting how many elements in the array are smaller than it. It then places the element into that position, displacing the element that was previously there. This displaced element is then moved to its correct position, and the process repeats until the cycle returns to the starting point.

How it Works

• Iterate through the array starting from cycleStart = 0 to n-2.

• Store the element at cycleStart in a temporary variable called item.

• Find Rank: Scan all elements to the right of cycleStart. Count how many elements are smaller than item. This count added to cycleStart gives the correct pos (position) for item.

• Skip Duplicates: If item is equal to the element currently at pos, increment pos to place item after the duplicates.

• Write: If pos is different from cycleStart, write item to arr[pos]. The value originally at arr[pos] becomes the new item to be placed.

• Rotate Cycle: Repeat the find-rank and write process for the new item until pos equals cycleStart.

• Move to the next cycleStart and repeat.