Sorting Of A Rotated Sorted Array

Posted: 6 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Given a rotated sorted array of size ‘N’ and let the elements of the given array be a1,a2,......,an . You need to sort the given array in increasing order.

For Example - Consider ‘N’ = 4 and the given array is [2,3,4,1] then the output should be [1,2,3,4].

A rotated sorted array is a sorted array in which each element is shifted ‘x’ (‘x’ >= 0 and ‘x’ <= ’N’) times to its right and the rightmost element is shifted to the beginning of the array.

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
Follow up :
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

Try Problem