What is Cyclic Sort?

Cyclic sort is an in-place, comparison-based sorting algorithm specifically designed for arrays containing numbers within a fixed, predefined range, such as 1 to N or 0 to N-1. It is highly efficient and straightforward, working by repeatedly placing elements in their correct, sorted positions through a series of swaps, effectively "cycling" through the array until every element is where it belongs.

Understanding the Core Concept

The fundamental idea behind cyclic sort is to ensure that each number X in the array is located at its correct index. For an array of N distinct numbers ranging from 1 to N, the number 1 should be at index 0, 2 at index 1, and so on, up to N at index N-1. If the numbers range from 0 to N-1, then 0 should be at index 0, 1 at index 1, and so forth.

The algorithm achieves this by iterating through the array. For each element, it checks if it's already in its correct position. If not, it swaps the element with the value that should be at its current position, continuing this process until the element is correctly placed. This creates a "cycle" of swaps until the element finally lands in its designated spot.

How Cyclic Sort Works (Algorithm Steps)

The cyclic sort algorithm proceeds iteratively, ensuring that each number finds its home:

1. Initialize Pointer: Start with a pointer, i, at the beginning of the array (index 0).
2. Determine Correct Position: For the element arr[i], calculate its correct index.
   • If numbers are from 1 to N: The correct index for arr[i] is arr[i] - 1.
   • If numbers are from 0 to N-1: The correct index for arr[i] is arr[i].
3. Check and Swap:
   • If arr[i] is not at its correct index (i.e., arr[i] is not equal to arr[correct_index]), swap arr[i] with the element at arr[correct_index]. This moves arr[i] closer to its correct spot, and brings a new element to arr[i]'s current position to be evaluated. Crucially, the pointer i does not increment after a swap because the new element at arr[i] might also be out of place and needs to be processed.
   • If arr[i] is at its correct index, then this element is sorted. Increment the pointer i to move to the next element.
4. Repeat: Continue steps 2 and 3 until the pointer i has traversed the entire array (i.e., i < N).

Key Characteristics and Efficiency

Cyclic sort is notable for its specific application and performance:

For a broader understanding of how this algorithm fits within the landscape of various sorting techniques, you can explore more about sorting algorithms.

Example Walkthrough

Let's sort the array [3, 1, 5, 2, 4] using cyclic sort. The numbers are from 1 to 5.

• Initial Array: [3, 1, 5, 2, 4]
• i = 0, arr[0] = 3:
  • Correct index for 3 is 3 - 1 = 2.
  • arr[0] (value 3) is not at arr[2] (value 5). Swap arr[0] and arr[2].
  • Array becomes: [5, 1, 3, 2, 4] (i remains 0)
• i = 0, arr[0] = 5:
  • Correct index for 5 is 5 - 1 = 4.
  • arr[0] (value 5) is not at arr[4] (value 4). Swap arr[0] and arr[4].
  • Array becomes: [4, 1, 3, 2, 5] (i remains 0)
• i = 0, arr[0] = 4:
  • Correct index for 4 is 4 - 1 = 3.
  • arr[0] (value 4) is not at arr[3] (value 2). Swap arr[0] and arr[3].
  • Array becomes: [2, 1, 3, 4, 5] (i remains 0)
• i = 0, arr[0] = 2:
  • Correct index for 2 is 2 - 1 = 1.
  • arr[0] (value 2) is not at arr[1] (value 1). Swap arr[0] and arr[1].
  • Array becomes: [1, 2, 3, 4, 5] (i remains 0)
• i = 0, arr[0] = 1:
  • Correct index for 1 is 1 - 1 = 0.
  • arr[0] (value 1) is at its correct index (arr[0] is 1). Increment i.
• i = 1, arr[1] = 2:
  • Correct index for 2 is 2 - 1 = 1.
  • arr[1] (value 2) is at its correct index (arr[1] is 2). Increment i.
• i = 2, arr[2] = 3:
  • Correct index for 3 is 3 - 1 = 2.
  • arr[2] (value 3) is at its correct index (arr[2] is 3). Increment i.
• i = 3, arr[3] = 4:
  • Correct index for 4 is 4 - 1 = 3.
  • arr[3] (value 4) is at its correct index (arr[3] is 4). Increment i.
• i = 4, arr[4] = 5:
  • Correct index for 5 is 5 - 1 = 4.
  • arr[4] (value 5) is at its correct index (arr[4] is 5). Increment i.
• i = 5: The loop terminates as i is no longer less than N.

The array is now [1, 2, 3, 4, 5], which is sorted.

Advantages and Use Cases

Cyclic sort's unique properties make it particularly useful for specific problems:

• Efficiency: It offers optimal time complexity of O(N) for its target use case, making it very fast for large datasets within its defined constraints.
• In-Place: Its O(1) space complexity is a significant advantage, as it does not require additional memory proportional to the input size.
• Simplicity for Specific Problems: While not a general-purpose sorting algorithm like quicksort or merge sort, its simplicity shines when dealing with:
  • Finding Missing Numbers: If a number is missing from the 1 to N range, its correct spot will be occupied by another number, or the range check will fail.
  • Identifying Duplicate Numbers: If two numbers are the same, one will try to occupy a spot already taken by its duplicate.
  • Finding the Smallest Missing Positive Number: A common variation where numbers outside the 1 to N range are ignored.
  • Finding all Duplicates or Missing Numbers: Extensions of the basic algorithm can efficiently list all such discrepancies.