Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Actually it is possible to merge in-place in O(n) time, but it's too complex to be asked in an interview. People are still researching on the topic and many research papers are available if you want.
Practically traditional merge algorithm (which uses auxiliary space) is better than in-place merge.
If asked in an interview you should mention the O(n^2) merging like insertion sort or the Quicksort. But that would defeat the goal of giving two sorted arrays as input.
public class sortInPlace {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {1,3,5,6,2,4,7};
sortArray(arr);
}
public static void sortArray(int []a)
{
int endOfFirstArray = 0,prevNum = -1;
if(a.length < 2)
{
return ;
}
if(a.length == 2)
{
if ( a[0] > a[1]) {
int temp = a[1];
a[1] = a[0];
a[0] = temp;
}
}
prevNum = 0;
for (int i = 1; i < a.length ; i++ )
{
if ( a[prevNum] > a[i])
{
break;
}
prevNum++;
}
int ptr2 = a.length -1 ,ptr1 = prevNum;
for (; ptr2 > ptr1 ; )
{
if (a[ptr2] > a[ptr1])
{
ptr2--;
}
else
{
int temp = a[ptr2];
a[ptr2] = a[ptr1];
a[ptr1] = temp;
int tempPtr2 = ptr2;
for (int j = tempPtr2 -1 ; j >=0 ; j--)
{
if (a[tempPtr2] < a[j] )
{
temp = a[tempPtr2];
a[tempPtr2] = a[j];
a[j] = temp;
}
tempPtr2--;
}
}
}
for (int i = 0 ; i < a.length ; i++)
{
System.out.println (a[i]);
}
}
}
it is possible in O(n) and the idea is like Insertion Sort
in case of array of increasing integers:
find the first element in array that is smaller than its previous element. (start of the second sorted sub-array)
swap this element with its previous one until it becomes bigger than its prev.
continue on the next index on the second sub-array until the end.
Merging two sorted lists can be done in O(N) time. The challenge here is doing it in place, which can be done in close to O(N) time. Basically, you just need to buffer elements from the first list that aren't ready to be inserted into the final list. Your intermediate lists will look like this:
FFF1111BBB222
F = element in final position
1 = element in 1st list
B = element in buffered head portion of first list
2 = element in 1st list
Keep track of the offsets of the first 1, the first B, and the first 2. When you do the normal merge step, if there are any Bs, grab them before you grab the 1s. You can think of this like a circular array for 1s, or it might make more sense to just think of it as a scratch area to save off 1s for later processing. Either interpretation leads to the same result.
One minor slowdown is that you can get a long run of 1s that are less than 2s, which builds up your buffer of Bs. Once you get to a B that is less than a 2, you'll need to shift over all the other Bs one to the left to buffer the 1 that is displaced by the new F.
When there are no Bs and the lead 1 sorts ahead of the 2, then you simply turn the 1 into an F.
When there are no Bs and the lead 2 sorts ahead of the 1, then you put the 2 in 1's old place, turning it into an F, then put the 1 in the 2's old place, turning it into a B.
When there ARE Bs and the lead 2 sorts ahead of the lead B, then you replace the lead 1 with the lead 2 (turned into an F) and put the lead 1 in the 2's old place (turned into a B).
Actually, I think I'd just bubble the lead 1 down into the 2s after any instance where the 2 sorts ahead of the 1. The worst case runtime is N squared, but if the lists are roughly interlaced, it's pretty fast.
What about the case wherein the buffer BBB gets overridden,for example the first B in BBB might contain a number from List 1 which is now being compare against 2. if(2 < 1), then say we need to insert 2 at the first B position.where will the value of 1 at the 1st B position go, we will have to push all elements one position to the right, increasing the complexity.
import java.util.Arrays;
public class SortSortedArrays {
public static void main(String[] args) {
int[] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };
int left = 0;
int right = 0;
int prev = Integer.MIN_VALUE;
System.out.println(Arrays.toString(arr));
//first find the start of the next array.
for(int i = 0; i < arr.length; i++)
{
if( arr[i] < prev )
{
right = i;
break;
}
prev = arr[i];
}
//sort the array
while(left < right && right < arr.length)
{
if( arr[left] >= arr[right] )
{
//shift digits to bring the digit from right
shiftDigits(arr,left,right);
right++;
}
else
{
left++;
}
}
System.out.println(Arrays.toString(arr));
}
public static void shiftDigits(int[] arr, int left, int right)
{
int digit = arr[right];
while(right > left)
{
arr[right] = arr[--right];
}
arr[left] = digit;
}
}
Order is close to N when the original array is completely sorted. Worst case is N^2. This sorts in place no extra space necessary.
Reposting with formatting
import java.util.Arrays;
//Order is close to N when the original array is completely sorted.
//Worst case is N^2. This sorts in place no extra space necessary.
public class SortSortedArrays {
public static void main(String[] args) {
int[] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11 };
int left = 0;
int right = 0;
int prev = Integer.MIN_VALUE;
System.out.println(Arrays.toString(arr));
//first find the start of the next array.
for(int i = 0; i < arr.length; i++)
{
if( arr[i] < prev )
{
right = i;
break;
}
prev = arr[i];
}
//sort the array
while(left < right && right < arr.length)
{
if( arr[left] >= arr[right] )
{
//shift digits to bring the digit from right
shiftDigits(arr,left,right);
right++;
}
else
{
left++;
}
}
System.out.println(Arrays.toString(arr));
}
public static void shiftDigits(int[] arr, int left, int right)
{
int digit = arr[right];
while(right > left)
{
arr[right] = arr[--right];
}
arr[left] = digit;
}
}
i can think only about O(n^2) solution : for each element in second sub array, find its place by binary search and evaluate amount of elements of second sub array that should be copied there, i mean if i have 1 2 5 6 7 3 4, we will find place of 3 and 4 by one binary search, but it is still O(n^2)
#include<stdio.h>
#include<conio.h>
void main(){
int arr[] = {1,4,5,7,8,9,2,3,6,10,11}, startIndex2dArray = 0;
printf("Array before sorting: ");
for(int i=0; i<10; i++){
printf("%d, ",arr[i]);
}
//Finding start index of 2nd array.
for(int i=0; i<10; i++){
if(arr[i] < arr[i+1]){
startIndex2dArray++;
}else{
startIndex2dArray++; break;
}
}
for(int j=0, k=0; j<startIndex2dArray; ){
if(arr[j] < arr[startIndex2dArray+k]){
j++;
}else{
int temoElmnt = arr[startIndex2dArray+k], p=startIndex2dArray+k, temp;
while(p>=j){
arr[p] = arr[p-1]; p--;
}
arr[j] = temoElmnt; j++;k++;
}
}
printf("\n\nArray after sorting: ");
for(int i=0; i<10; i++){
printf("%d, ",arr[i]);
}
getch();
}
public static void SortTwoMergedArrays(int[] data)
{
int sIndex = 0;
for (int i = 0; i < data.Length; i++)
{
if (data[i] > data[i + 1])
{
sIndex = i + 1;
break;
}
}
for (int i = 0; i < sIndex; i++)
{
if (data[i] > data[sIndex])
{
int tmp = data[i];
data[i] = data[sIndex];
data[sIndex] = tmp;
//then replace item in second array
for (int t = sIndex; t < data.Length-1; t++)
{
if (data[t] > data[t + 1])
{
tmp = data[t];
data[t] = data[t + 1];
data[t + 1] = tmp;
}
else
break;
}
}
}
}
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{int i;
int a[]={1,4,5,7,8,9,2,3,6,10,11};
for(i=1;i<11;i++){
if(a[i-1]<a[i]){continue;}
else
{
int val=a[i];
for(int k=i-1;k>=0;k--)
if(a[k]>val)
{a[k+1]=a[k];}
else
{a[k+1]=val;break;}
}
}
for(int i=0;i<11;i++)
cout<<a[i];
getch();
}
public class a
{
public static void main(String[] args)
{
int k=0;
int a[]={1,3,5,7,9,2,4,6,8};
for(int i=1;i<a.length;i++)
if(a[i-1]<a[i])
continue;
else
{
int v=a[i];
for(;k<i&&a[k]<a[i];k++);
System.arraycopy(a,k,a,k+1,i-k);
a[k]=v;
k+=1;
}
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
}
def msort(array):
if len(array) <=1:
return
left_index = 0
right_index = 1
while right_index < len(array):
if array[right_index] < array[right_index-1]:
break
right_index += 1
if right_index == len(array):
return
#merge the left and right part
while left_index < right_index and right_index < len(array):
if array[left_index] <= array[right_index]:
left_index += 1
else:
tmp = array[right_index]
#move elements [left_index,right_index) one step to right
for i in range(right_index,left_index,-1):
array[i] = array[i-1]
array[left_index] = tmp
left_index += 1
right_index += 1
return
I have an approximately O(n) solution. What you want to do is find the beginning of the second sub-array by starting at the end, and decrementing the reference index by 1 until either the current element is less than the element previous to it in the array, or if the reference index becomes 0 (in which case, the two sorted sub-arrays are already fully sorted). We'll call the resulting index "r". Then, set another index at the beginning of the array, we'll call that index "l".
Now, iterate the "l" pointer through the array. Compare the value at a[l] with the value at a[r]. If a[l] is less than a[r], increment l. Otherwise, swap the values at l and r, and then increment r. When both l and r have incremented past the end of the array, the sorting is finished.
Java code looks like:
public void sort(int[] a) {
int left = 0;
int right = a.length - 1;
// find beginning of second sub-array
while(right != left || a[right] > a[right-1]) {
right--;
}
while(right != a.length && left != a.length) {
if(a[left] < a[right]) {
left++;
} else {
swap(a, left, right);
right++;
}
}
}
public void swap(int[] a, int l, int r) {
int tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}
Not most efficient way, but a pretty simple one:
int * sortInPlace(int * arr, int size){
int * secArr = arr;
int i = 0;
for(i=0; i<size-1; i++){
if((*secArr)>(*(secArr+1))){
secArr++;
break;
}
secArr++;
}
for(int j=i+1;j<size;j++){
int * tempArr = arr;
while(tempArr != secArr){
if(*tempArr > *secArr){
int temp = *tempArr;
*tempArr = *secArr;
*secArr = temp;
}
tempArr++;
}
secArr++;
}
return arr;
}
Here is my take on the problem.
Logic:
a. We need to know the indexes of the two arrays.
b. Start merging from the end of two arrays.
c. Compare FirstArray[i] and SecondArray[j],
if(SecondArray[j] > FirstArray[i])
{
j--;
}
That was easy. Now consider the opposite case, when FirstArray[i] > SecondArray[j]. We will swap. But now the FirstArray is o longer a sorted array as it may be possible after swapping FirstArray[i] < FirstArray[i-1].
And we do not want to bubble this element as that will only increase the time complexity. What we will do is that we will keep the element there. And if (FirstArray[i] < FirstArray[i -1]) we will decrement i, as in FirstArray[i -1] becomes the candidate for merging at the end of the array.
//
if (FirstArray[i] > SecondArray[j])
{
Swap(FirstArray[i], SecondArray[i]);
if (FirstArray[i] < FirstArray[i-1])
i--;
}
If we continue this process, then FirstArray element distribution will end up as an array of two sorted arrays. We apply the same algo on FirstArray now.
Lets look at how this will work for our sample.
1. [ 1 4 5 7 8 9 2 3 6 10 11] // i = 5, j = 10 Compare 11 and 9. Since SecondArray > FirstArray, we will decrement j
2. [ 1 4 5 7 8 9 2 3 6 10 11] // i = 5, j = 9, Compare 10 and 9--> j needs to be decremented
3. [ 1 4 5 7 8 9 2 3 6 10 11] // i = 5, j = 8 Compare 6 and 9 ---> values need to be swapped
4. [ 1 4 5 7 8 6 2 3 9 10 11] // But now you can see First Array is no longer a sorted array. We will compare FirstArray[i] and FirstArray[i -1]. Since 8 > 6, we will decrement i as well
5. [1 4 5 7 8 6 2 3 9 10 11] // i = 4, j = 7, compare value 8 with 3, clearly a swapping is required. we will do the same thing as above step
6. [1 4 5 7 3 6 2 8 9 10 11] // i = 3, j = 6, compare 7 with 2.
7. [ 1 4 5 2 3 6 7 8 9 10 11]
Now if you look at the FirstArray [1 4 5 2 3 ], its again a mix of sorted array. We will do the same steps of First Array.
[ 1 4 5 2 3]
[1 4 3 2 5]
[1 2 3 4 5]
Ans we will get the sorted array.
1. Find the last element of both sorted sub arrays.
2. Let's say i=index of last element subarray1 j= index of last element subarray2.
3. while(j>=i) {
If(array[i] > array[j]) {
swap(array[i], array[j])
i--;
} else {
j--;
}
}
4. Finally array will contain sorted list.
It doesn't work for the below case..
say the array to be [1,2,3,4,5,7,6]
in this array.. the two subarrays are [1,2,3,4,5,7] [6]..
according to your logic..
i=5(i.e. index of last element of subarray1),
j=6(i.e. index of last element of subarray2)
the 3rd step of while loop condition ( j> =i) never quits..as you keep decrementing i.. finally you get the exception when i=-1
Because the index of last element of subarray1 is always less than or equal to index of last element of subarray2 i.e. (i<=j).. the while loop condition should also contain condition i>0, i..e. while(i>0 && i<=j) should be the condition to successfully bypass the above use case of [1,2,3,4,5,7,6] , you will never get the codition of j<n (bcz j is decremented in the while loop) & j>0 ( bcz before j reaches negative values..it has to cross i first)
Yes you are correct.. Boundary conditions i missed out. Apart from that I hope its correct.
This can be done using heap sort with has the O(nlgn)
The key is to build min heap here and keep on shrinking the array size from left which is the sorted in increasing order
The condition that the min heap needs to follow is that the value of children is greater or equal to the parent and this can be considered as the loop invariant condition => loop invariant is the condition which needs to be satisfied in every loop inorder to sort the seq
here is the algo
1) create min heap - O(n)
2) for range starting from 0 to n-1; call min_heapify on Array[ i to n]
which will push the minimum value to top and we can consider the heap from i+1 index in the next loop
there by building sorted array
public static int[] merge_sorted(int a[], int b[]) {
int arr[] = new int[a.length+b.length];
int end_position = a.length+b.length -1;
int first_array = a.length -1;
int second_array = b.length -1;
while (end_position >= 0) {
if (first_array >= 0 && second_array >= 0) {
arr[end_position--] = a[first_array] > b[second_array] ?
a[first_array--] : b[second_array--];
}
if (first_array >= 0 && second_array < 0) {
arr[end_position--] = a[first_array--];
}
if (second_array >= 0 && first_array < 0) {
arr[end_position--] = a[second_array--];
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
return arr;
}
Here is O(N) time algorithm. It's kinda hard to explain in words so I wrote a program. It may not seem O(N) because of so many loops but I guarantee that it's O(N). I have tested for given two inputs and some other special cases. You may try more others. If you have counter example then please let me know.
def sort(lst):
s1=0
s2=1
#Find start index of second list
while s2 < len(lst) and lst[s2-1]<lst[s2]:
s2+=1
#sorting loop
while s1<len(lst) and s2<len(lst) and s1<s2:
if lst[s1] >= lst[s2]:
index=s2
count=0
#finding the count of elements which need to be swapped
while index< len(lst) and lst[s1] >= lst[index]:
count+=1
index+=1
index=s2
#swapping elements
swap(lst,s1,index,count)
s1+=count
else:
s1+=1
print(lst)
def swap(lst,s1,s2,count):
while count!=0:
lst[s1],lst[s2] = lst[s2] , lst[s1]
s1+=1
s2+=1
count-=1
lst=[1, 5, 10, 15, 20, 2, 3, 4]
lst=[1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11]
sort(lst)
Here is the c Code for above program
It forst looks for the starting point of second array
and then sorts it
#include<stdio.h>
main()
{
int i,j,t,n,l,k;
printf("Enter the size of the array : ");
scanf("%d",&n);
int a[n];
printf("\n\nEnter tha array elements :\n\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
//finding starting pos of the 2nd array
l=-1,j=n;
for(i=1;i<n;i++)
if(a[i-1]>a[i])
j=l=i;
//sorting the array
for(i=0;i<l;i++)
{
if(a[j]<a[i])
{
t=a[i];
a[i]=a[j];
for(k=j+1;k<n && a[k]<t;k++)
a[k-1]=a[k];
a[k-1]=t;
}
}
//printing result
printf("\n\n\n\n\n");
printf("The sorted array is :\n\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
This is how I did it:
import java.util.Arrays;
public class Two_Sub_Sorted_Array {
public static void main(String[] args) {
int[] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11};
sort(arr);
}
public static void sort(int[] a) {
int sec = 0;//first index of second array
for (int i = 0; i + 1 < a.length; i++) {
if(a[i] > a[i + 1]) {
sec = i + 1;
break;
}
}
//first array
int[] a1 = Arrays.copyOfRange(a, 0, sec);
//second array
int[] a2 = Arrays.copyOfRange(a, sec, a.length);
System.out.println("a1: " + Arrays.toString(a1));
System.out.println("a2: " + Arrays.toString(a2));
//result array
int[] res = new int[a.length];
int c1 = 0, c2 = 0, limit = 0;
boolean arr1 = false;
//sorting
for (int i = 0; i < res.length; i++) {
if(a1[c1] < a2[c2]) {
res[i] = a1[c1++];
} else if(a1[c1] > a2[c2]) {
res[i] = a2[c2++];
} else if (a1[c1] == a2[c2]) {
res[i] = a1[c1++];
res[++i] = a2[c2++];
}
if(c1 == a1.length){
limit = i + 1;
arr1 = true;
break;
} else if (c2 == a2.length) {
limit = i + 1;
break;
}
}
if(arr1){
for (int i = limit; i < res.length; i++) {
res[i] = a2[c2++];
}
} else {
for (int i = limit; i < res.length; i++) {
res[i] = a1[c1++];
}
}
//printing the result
System.out.println(Arrays.toString(res));
}
}
Output:
a1: [1, 4, 5, 7, 8, 9]
a2: [2, 3, 6, 10, 11]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
is this an in place algorithm , you are making use of another data structure res right ?
It sounds like it's essentially an in-place merge operation. The code below should do it in O(N^2) time, by doing a normal merge, but inserting the element in the correct position in the second array if it's out of position in the first.
There's a solution here: h2database.googlecode.com/svn/trunk/h2/src/tools/org/h2/dev/sort/InPlaceStableMergeSort.java that is O(N*log(N)) but it's not trivial.
import java.util.Random;
public class SortTwoSubArrays {
// An array contains two sub- sorted arrays. Give an inplace algorithm to sort two sub arrays.
//
// for ex: I/P: 1 4 5 7 8 9 2 3 6 10 11
// O/P: 1 2 3 4 5 6 7 8 9 10 11
public static void main(String[] args)
{
{
int [] arr = {1, 4, 5, 7, 8, 9, 2, 3, 6, 10, 11};
sortSub(arr);
for(int v : arr)
{
System.out.print(v + ", ");
}
System.out.println();
}
{
Random rand = new Random();
int [] arr = new int[20];
int at = 0;
for(int i = 0; i < 10; i++)
{
at += rand.nextInt(5);
arr[i] = at;
}
for(int i = 10; i < 20; i++)
{
at += rand.nextInt(5);
arr[i] = at;
}
sortSub(arr);
for(int v : arr)
{
System.out.print(v + ", ");
}
System.out.println();
}
}
public static void sortSub(int [] arr)
{
int cut = -1;
for(int i = 1; i < arr.length; i++)
{
if(arr[i-1] > arr[i])
{
cut = i;
break;
}
}
if(cut == -1)
return;
int aAt = 0;
int bAt = cut;
System.out.println("Found cut at " + cut);
while(true)
{
System.out.println(aAt + ", " + bAt);
if(aAt == bAt || bAt == arr.length)
break;
//If current a-value is largest, simple; just inc a counter
if(arr[aAt] < arr[bAt])
{
aAt++;
}
//If not, we have to put the b-value into the 'sorted' part
//and then shift the a-value into the b-array; this is O(N)
//worst case
else
{
int temp = arr[aAt];
arr[aAt] = arr[bAt];
int curBAt = bAt;
while(true)
{
//insert here
if(temp < arr[curBAt+1] || curBAt+1 == arr.length)
{
arr[curBAt] = temp;
break;
}
//keep shifting and looking
{
arr[curBAt] = arr[curBAt+1];
}
curBAt++;
}
aAt++;
//curBAt++;
}
}
}
}
Yes, this question seems to be asking for an in-place merge algorithm.
Doing the insertion sort like steps, should work to give us an O(n^2) algorithm.
Getting an O(n) time merge algorithm is quite difficult, and research papers have been written about it (after being open for some time).
Then why not use a simple quick sort ???? Why pick an algorithm with N^2 complexity ???
just too much hardwork for no specific reason...
we can do it O(n) . The given input is a two sorted array merged together . We just need to find the index of an element which has a condition (array[index-1] < array[index] ) && (array[index] > array[index+1]) . Then just a simple merge will do the job
@Mr.karthik.p: The issue is that a merge is really not so simple when you don't have extra space.
@Bevan: That makes sense if you want an O(n log n) solution. You wouldn't be taking advantage of the fact that the array is just two sorted arrays back-to-back (instead of being just random data), but it's still a decent algorithm all in all. You probably want to use an in-place heapsort because quicksort does use just a little bit of extra space (logarithmic).
This is my try.......... Is this in space algorithm.........?
import java.io.*;
class Inplace
{
public static void main(String q[])
{
DataInputStream dis=new DataInputStream(System.in);
int n1,n2,n,a[]=new int[20],i,j;
System.out.println("Enter the length ");
try
{
n2=Integer.parseInt(dis.readLine());
System.out.println("Enter the elements : ");
n1=n2;
for(i=0;i<n2;i++)
{
a[i]=Integer.parseInt(dis.readLine());
if((i!=0)&&(a[i]<a[i-1]))
{
n1=i;
}
}
i=n1-1;j=n2-1;
while((i>=0)&&(j>=n1))
{
if(a[i]<a[j])
{
j-- ;
}
else
{
int c=a[i],k;
for(k=i;k<j;k++)
a[k]=a[k+1];
a[k]=c;
i--;
j--;
n1--;
}
}
System.out.println("Sorted Numbers are");
for(i=0;i<n2;i++)
System.out.println(a[i]);
}
catch(IOException e)
{
System.out.println(e);
}
}
}
This is my try....... Is this inspace algorithm.........?
import java.io.*;
class Inplace
{
public static void main(String q[])
{
DataInputStream dis=new DataInputStream(System.in);
int n1,n2,n,a[]=new int[20],i,j;
System.out.println("Enter the length ");
try
{
n2=Integer.parseInt(dis.readLine());
System.out.println("Enter the elements : ");
n1=n2;
for(i=0;i<n2;i++)
{
a[i]=Integer.parseInt(dis.readLine());
if((i!=0)&&(a[i]<a[i-1]))
{
n1=i;
}
}
i=n1-1;j=n2-1;
while((i>=0)&&(j>=n1))
{
if(a[i]<a[j])
{
j-- ;
}
else
{
int c=a[i],k;
for(k=i;k<j;k++)
a[k]=a[k+1];
a[k]=c;
i--;
j--;
n1--;
}
}
System.out.println("Sorted Numbers are");
for(i=0;i<n2;i++)
System.out.println(a[i]);
}
catch(IOException e)
{
System.out.println(e);
}
}
}
Make one pointer point to the beginning of the 2nd sub-array and another pointer to the beginning of the first sub-array. Keep on comparing the values of these to pointers and change position if required. O(1) space O(n) time.
Nope. You are wrong. the second swap that you did will not occur as pointer 2 will go to null. At least try and make some sense!
If the sub arrays are already sorted, just use pointers and iterate through them
a = {[1,3,5], [2, 4, 6]}
...
a = {[1,2,5], [3, 4, 6]}
...
a = {[1,2,3], [5, 4, 6]}
...
a = {[1,2,5], [4, 5, 6]}
I think this is a trick question for 2 reasons:
- Karan March 09, 20131) Whether the array is sub-sorted or not, an in-place quick sort can be done in O(nlogn)
2) So if we are really looking for a O(n) solution, then why wouldn't that solution be used in the "merge" step of a standard merge-sort, making the merge-sort an in-place algorithm (which it is obviously not) ?
Therefore, I don't think it can be done in less than O(nlogn)