Sort a half-sorted array

Easy

0/40

Average time to solve is 10m

7 upvotes

Asked in company

Problem statement

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.

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: 1sec

Sample Input 1:

1
5
1 5 2 3 6

Sample Output 1:

1 2 3 5 6

Explanation for sample input 1:

The given array can be broken into two sorted partitions as P1={1, 5} and P2={2, 3, 6}. After sorting the entire array in ascending order, we get {1, 2,3, 5, 6}.

Sample Input 2:

1
7
2 3 8 1 7 10 15

Sample Output 2:

1 2 3 7 8 10 15

Hint 1

Hint 2

Sort the entire input array

Approaches (2)

Approach 1

Approach 2

Sort the entire input array

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

Time Complexity

O(N * log(N)), where ‘N’ is the size of the array.

If quick sort or merge sort is used.

Space Complexity

O(1)

As we are using constant extra memory.

(100% EXP penalty)

Sort a half-sorted array

Console