Last Updated: 29 Dec, 2020
Sort a half-sorted array
Easy
Asked in company
You are given an arbitrary array of integers of size ‘N’ which consists of two partitions sorted in non-decreasing order. You need to sort the entire array in ascending order. In other words, given an array of integers in which elements are divided into two partitions such that both the partitions are individually sorted, you need to sort the entire 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: 1sec
Approaches
A naive or brute force approach for this problem is to simply sort the entire given array, ignoring the fact that it consists of two already sorted partitions. We can use a quick sort or merge sort algorithm to sort the array efficiently. Also, most of the languages have their in-built sort methods which are quite efficient in terms of time and space complexities.
Follow the links below to get in-depth information about these algorithms-
Quick Sort - https://en.wikipedia.org/wiki/Quicksort
Merge Sort - https://en.wikipedia.org/wiki/Merge_sort
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