# [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.