Last Updated: 5 Jul, 2021
Sort A Partial Sorted Array
Easy
Asked in company
Ninja has been given an arbitrary array of integers of size ‘N'. You can think of the array as the concatenation of two individually sorted arrays in non-decreasing order. Ninja needs to sort the entire array in ascending order.
Can you help Ninja to sort the array?
Note :
Both the partitions need not be of the same size.
Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case consists of a single integer, representing the size of the array.
The second line of each test case contains 'N' space-separated integers, denoting the elements of the array.
Output Format :
For each test case, print the elements of the array in the space-separated form which is sorted in non-decreasing order.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function. Also, you need to update the given array in place.
Constraints :
1 <= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Approaches
An efficient solution will be to use a modified version of merge() function used in the merge sort algorithm.
- First, create an auxiliary array ‘ans’ of size N which will be used to store the final sorted array.
- Now, first of all, find the pivot point in the given array. This point will be the point where the second sorted partition begins. Let the pivot index be called ‘pivot’
To find pivot, we can use the logic that it will be the first index where arr[i-1]>arr[i]. We can use a simple for loop to check this condition and find our required index. - One thing to note here is that if pivot=0, it means that the array consists of only one partition and the array is already sorted. We simply return in this case.
- Once we have a pivot, we initialize three variables i=0, j=pivot, and k=0. i will be used to traverse over the first partition, j will be used to traverse over the second partition and k will keep track of the temporary array in which we store the elements in sorted order.
- We use a while loop to keep storing the elements in a temporary array in ascending order, by picking one element from a single partition at a time until I < pivot and pivot < n.
- After this, we copy the elements which are left in both the partitions one by one in the temporary array.
- Finally, copy back the contents of the temporary array in the given array and return it.
Similar problems