## Given problem

Given an array nums = `{3, 1, 5, 4, 2}`. How to use Cyclic sort for this array.

## Solution of Cyclic Sort

When using Cyclic Sort, there are some things that we need to take note:

• At a specific position in an array, we always try to arrange it to the correct position by comparison `nums[start] != nums[current]`.
• If an element lied in the correct position, process the next element.

Below is the source code of Cyclic Sort.

``````public static void cyclicSort(int[] nums) {
int start = 0;

while (start < nums.length) {
int current = nums[start] - 1;

if (nums[start] != nums[current]) {
swap(nums, start, current);
} else {
++start;
}
}
}

private static void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}

public static void main(String[] args) {
int[] nums = {3, 1, 5, 4, 2};
//        int[] nums = {2, 6, 4, 3, 1, 5};
//        int[] nums = {1, 5, 6, 4, 3, 2};

cyclicSort(nums);
System.out.println(Arrays.toString(nums));
}
``````

The complexity of this Cyclic Sort:

• Time complexity: O(n)
• Space complexity: O(1)

## When to use

• When our array has a range from 0 to n.

## Benefits and Drawbacks

1. Benefits

• It improves our sorting for an array simply because it only needs `O(n)` for time complexity.
• Its implementation is easy.
2. Drawbacks

• Only use in some specific use cases.