Cyclic Sort Made Simple: Learn the Basics and How It Works

Cyclic sort is an in-place and unstable sorting algorithm that is specifically designed to efficiently sort arrays where numbers are in a known range like from 1 to N.

How does it work?

Let’s take the following array as an example. We need to sort it in ascending order.

The algorithm works by choosing an element and puts it at its correct index. It starts with the first element.

In the example array, the algorithm chooses the first element 5. Its correct index is 4.

The algorithm swaps 5 with the element at the correct index of 5 i.e. element 2 present at index 4.

The algorithm now checks whether the element at the position of the control variable i is in its correct position: Is 2 in its correct position? No. So, the control variable will not increment its position.

The algorithm will swap 2 with 4 (as the correct index of 2 is index 1).

It will again check: is element 4 is at its correct index? No, it isn’t. The correct index of 4 is index 3.

So, it will swap element 4 with element 3 (as the correct index of element 4 is index 3).

Now, it will check again: is element 3 at its correct index? No, it isn't. The correct index of 3 is index 2.

So, element 3 will be swapped with element 1.

Now, the algorithm checks once again: is element 1 at its correct index? Yes, it is!

So, the algorithm will move to the next index and once again check if that element is at its correct index.

Is element 2 at its correct index? Yes, it is. The algorithm continues this process until it reaches the end of the array.

💡	You might have already realized that the correct index for an element is its value - 1, if the range of numbers in the array is 1 to N.

Space Complexity

As this algorithm is an in-place sorting algorithm, it does not require any auxiliary space. So, its space complexity is O(1).

Time Complexity

We have two scenarios here: the worst case and the best case.

Worst Case

The worst case happens when every number is in the wrong place in an array with a known range (say, 1 to N). The sample array used above, [5, 4, 1, 3, 2], is an example of the worst case. Let's calculate how many times the algorithm performed checks.

In the example array, total 4 swaps and 5 checks were made. After all swaps were performed at the first index, the element at that index was checked once again. Therefore, there were a total of 5 checks.

In general, N - 1 swaps and N checks would be made. As in each swap, 1 check is performed. So, there would be a total of $2N-1$ checks made.

Therefore, the worst-case time complexity of cyclic sort algorithm is O(N).

Best Case

The best case happens when the array is sorted in the desired order. In that case, the algorithm checks each element once and does not perform any swaps. Therefore, the best-case complexity is O(N).

Example Code

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 1, 4};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void sort(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            // Assuming range of array is 1 to N
            int correctIndex = arr[i] - 1;
            if (arr[i] != arr[correctIndex]) {
                swap(arr, i, correctIndex);
            } else {
                i++;
            }
        }
    }

    static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }
}

Conclusion

Cyclic sort is a highly efficient algorithm for sorting arrays with elements in a known range, such as from 1 to N. It operates in-place, requiring no additional space, which makes it space-efficient with a complexity of O(1). The algorithm's time complexity is O(N) in both the best and worst cases, making it a reliable choice for sorting tasks where the range of numbers is predetermined. By understanding the mechanics of cyclic sort, you can effectively apply it to relevant sorting problems, optimizing performance and resource usage.

⭐ Check out the DSA GitHub repo for more code examples.