# Sorting Of A Rotated Sorted Array

Posted: 6 Jan, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### For Example - [3,4,1,2] is a rotated sorted array in which each element is shifted two times to its right.

##### Input format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ denoting the size of the given rotated sorted array.

The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the given rotated sorted array.
``````
##### Output Format :
``````For each test case, print a single line containing 'N' single space-separated integers representing the elements of the sorted array.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 50
1 <= N <= 10^4
-10^9 <= a[i] <= 10^9

Where ‘T’ is the total number of test cases, ‘N’ is the size of the array and a[i] is an element of the array.

Time Limit: 1 sec
``````
``````Don’t use the sort() function.
``````
Approach 1
• Find the rotation point is the rotated array using linear search and store its index in a variable ‘shiftCount’.
• Run a while loop ‘shiftCount’ times and in each iteration do the following:
• Store the element at index 0 in variable ‘leftElement’
• Shift each element with index > 0 to its left.
• Store the element stored in ‘leftElement at the last index.

Before Iteration

After Iteration