# [Solved] Sort the Circular Rotated Array in O(n) Time| Algorithm | Code

**Problem statement:** You have given a circular rotated array. Write a program to sort the circular rotated array.

**Example**

Input (Circular Rotated Array): [3, 4, 5, 1, 2]

Output (Sorted Array): [1, 2, 3, 4, 5]

This question was asked in one of Byju’s coding interview. Basically, they asked to find the given element in a circular rotated array in order of `O(log(n)`

time.

To solve this problem, you have to rotate the array and then do the binary search.

Let’s continue with the sorting circular rotated array.

Table of Contents

#### Algorithm

- Find the index of the smallest element in the array (says
`index_smallest`

). - Reverse all the left side elements of the smallest element in the array (excluding element at
`index_smallest`

) - Reverse all the right side elements of the smallest element in the array (including element at
`index_smallest`

) - Now, reverse the complete array.

#### Explanation

- Let’s take an example of a circular rotated array
`[3, 4, 5, 1, 2]`

. - Smallest element is at position “3” (
`index_smallest`

= 3). - Reverse all elements from index “0” to “2”. The resultant array will be
`[5, 4, 3, 1, 2]`

. - Reverse all elements from index “3” to “4”. The resultant array will be [5
`, 4, 3, 2, 1]`

. - Now reverse all the elements in the array. You will get a complete sorted array as
`[1, 2, 3, 4, 5]`

.

You can solve this problem in any programming language of your choice.

#### Python Program

In Python, you can reverse the list using extended slice syntax (just one line code). But, in competitive programming, you will be encourage to write your own logic.

**Code**

```
# function to reverse the array list
def reverse_array(arr, start=0, end=0):
if end == 0:
end = len(arr)-1
while start<=end:
temp = arr[start]
arr[start] = arr[end]
arr[end] = temp
start += 1
end -= 1
# function to sort cicular roated array list
def sort_circular_rotated_array(arr):
index_smallest = 0
for i in range(len(arr)-1):
if arr[i]>arr[i+1]:
index_smallest = i+1
break
reverse_array(arr=arr, end=index_smallest-1)
reverse_array(arr=arr, start=index_smallest)
reverse_array(arr=arr)
return arr
arr = [3, 4, 5, 1, 2]
print(sort_circular_rotated_array(arr))
```

**Output**

[1, 2, 3, 4, 5]

#### Complexity

It takes `O(n)`

time to find the smallest element in the array. For reversing array it will take `O(n)`

times in worst-case scenario.

We are calling the reverse array function thrice but each element will get displaced twice so the overall complexity for reversing array is `2*O(n)`

.

Total complexity is `O(n)+2*O(3)`

which is equivalent to `O(n)`

. So, the overall time complexity of this algorithm is `O(n)`

.

We are not creating any new array and all the elements in the array are getting changed in place. So, the space complexity is `O(1)`

i.e. constant space.

Hope you learned a new trick to sort the circular rotated array and to find the element in the circular rotated array in minimum time.