Sort A Partial Sorted Array

Easy
0/40
Average time to solve is 10m
profile
Contributed by
2 upvotes
Asked in company
OYO

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
6
7 10 12 3 4 5
Sample Output 1 :
3 4 5 7 10 12
Explanation for sample input 1 :
The given array can be broken into two sorted partitions as P1={7, 10, 12} and P2={3, 4, 5}. After sorting the entire array in ascending order, we get {3, 4, 5, 7, 10, 12}.
Sample Input 2 :
1
5
1 5 10 2 6
Sample Output 2 :
1 2 5 6 10
Hint

Can we use the merge function of MergeSort?

Approaches (1)
Use Merge Function

An efficient solution will be to use a modified version of merge() function used in the merge sort algorithm.

  1. First, create an auxiliary array ‘ans’ of size N which will be used to store the final sorted array.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. After this, we copy the elements which are left in both the partitions one by one in the temporary array.
  7. Finally, copy back the contents of the temporary array in the given array and return it.
Time Complexity

O(N), where ‘N’ is the number of elements in the array. 

 

As we are using a two-pointer approach to traverse over the array.

Space Complexity

O(N), where ‘N’ is the number of elements in the array. 

 

As we are using extra space for the temporary array.

Code Solution
(100% EXP penalty)
Sort A Partial Sorted Array
Full screen
Console