What is a cyclic sort algorithm?

Key takeaways:
Cyclic sort is a comparison-based, in-place sorting algorithm designed for arrays with a fixed range of values, making it both efficient and straightforward.
The algorithm works by repeatedly placing elements in their correct positions through a series of swaps, cycling through the array.
Cyclic sort is particularly useful when the values in an array range from $1$ to $n$ , minimizing extra space usage as it sorts directly within the array.
The algorithm is unstable but is highly effective in solving specific problems like missing number or duplicate number detection.
It has a time complexity of $O(n)$ , making it highly efficient for certain scenarios, especially when sorting integers within a known range.

Sorting is a fundamental operation in computer science, allowing us to arrange data in a specific order for efficient analysis and decision-making. Various sorting algorithms have been developed, each with strengths and weaknesses. One such algorithm is cyclic sort, a simple and efficient algorithm that works particularly well when dealing with a range of values within a fixed interval.

Cyclic sort

Cyclic sort is a comparison-based sorting algorithm that works for arrays containing values within a specific range. It’s an in-place, unstable algorithm that aims to sort the elements by arranging them in their correct positions, one at a time, through a series of swaps. The basic idea behind cyclic sort is to iterate through the array and place each element in its intended position until the entire array is sorted. It is based on the insight that subsequences of numbers in the input array that are not in sorted order describe cycles and that placing each number in its correct position removes them.

What does it mean to have a cycle?

In a cycle, numbers that are not in their correct index are essentially part of a loop, where each number belongs to a different position. For example, if a number, $3$ , at index $0$ should be at index $2$ , the number $2$ at index $2$ should be at another index $1$ , and the number $1$ at index $2$ should be at index $0$ , then these numbers form a cycle. The process of cyclic sort ensures that each number is placed at its correct position by following this cycle and swapping elements accordingly.

Now, let’s look at the following illustration to get a better understanding of the algorithm:

def cyclic_sort(arr):
    n = len(arr)  
    for i in range(n):
        while arr[i] != i + 1: 
            correct_index = arr[i] - 1 
            arr[i], arr[correct_index] = arr[correct_index], arr[i] 
    return arr 
# Driver code
def main():
    nums = [
        [1, 3, 2, 5, 4], 
        [2, 4, 5, 1, 3], 
        [1, 2, 4, 3], 
        [3, 1, 5, 6, 4, 2]
    ]
    for i in range(len(nums)):
        print(i + 1, ".\tArray before cyclic sort = ", nums[i], sep="")
        print("\tArray after cyclic sort = ", cyclic_sort(nums[i]), sep="")
        print("-" * 100)
if __name__ == '__main__':
    main()

Cyclic sort example

Code explanation

Lines 2–3: We get the length of the array and traverse it.
Line 4: We move in the array cyclically until the current element is in its correct position.
Line 5: We calculate the correct index for the current element.
Line 6: We swap the current element with the element at its correct index.
Line 7: We return the sorted array.

If you're prepping for technical interviews, understanding these algorithms and patterns can be a game changer. For LeetCode pattern-based problems, check out our course on Coding Interview Patterns.

When and why to use cyclic sort?

Cyclic sort is especially useful when dealing with arrays that contain consecutive integers within a fixed range. It is effective in the following cases:

Detecting missing numbers: In arrays where one or more elements are missing, cyclic sorting helps efficiently identify those missing numbers.
Finding duplicates: It can also be used to find duplicate numbers in an array, as it quickly places elements where they belong and identifies those that are out of place.

We also have a detailed Answer on When and why do we use cyclic sort?

Time and space complexity

Time complexity: $O(n)$ , as each element is moved at most once.
Space complexity: $O(1)$ , since no additional space is required for sorting beyond the input array.

To further enhance your knowledge and skills in coding interviews, we recommend a specially designed path, Educative 99. This path offers interactive lessons that give hands-on experience with coding problems and opportunities to test and refine your solutions.

Limitations of cyclic sort

Unstable sorting: Cyclic sort is unstable, meaning it doesn’t preserve the relative order of equal elements.
Limited use case: It is effective primarily for arrays with consecutive integers or specific ranges, limiting its general applicability.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

Why is cyclic sort efficient for consecutive integers?

It is efficient because it places each element in its correct position through a series of swaps, allowing the algorithm to run in $O(n)$ time with minimal space overhead.

Is cyclic sort a stable sorting algorithm?

No, cyclic sort is not stable, meaning it doesn’t maintain the relative order of equal elements.

What are the primary use cases of cyclic sort?

Cyclic sort is most commonly used for detecting missing numbers, finding duplicates, and efficiently sorting arrays with elements in a consecutive range.

Can cyclic sort handle arrays with repeated values?

Cyclic sort can handle arrays with repeated values, but it is best suited for arrays containing unique consecutive integers.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources