CareerCup

Use Heap sort here. Steps will be:
1. Make max-heap for both the arrays. First element of both the arrays will be the largest for that array now.
2. Max of first elements of both the arrays will be swapped with the last of array B.
3. Heap size will be decreased by 1 for array B.
4. Again make the max heap for the array where we found and swapped the largest element.
5. repeat step 2 to 4 until Heap size for B becomes 0.
6. Run Heap sort on A.

Space Complexity: O(1), Time Complexity: O(nlogn)

I think constant space , means merge should be done in one of the two array having largest size which can accommodate elements of other array without using extra memory. Is this question ? please clarify .

No sorry the larger array is not large enough to accommodate elements of smaller array. I mean there are no empty elements in larger array.

let's n is the length of the first sorted array and m is the length of the second sorted array.
and c[MAX] is the array which will contain the sorted and merged data.

int i = 0, j = 0, k = 0;
while(i <= n && j <= m)
{
if(a[i] < b[j])
c[k++] = a[i];
else

}

let's n is the length of the first sorted array and m is the length of the second sorted array.
and c[MAX] is the array which will contain the sorted and merged data

int i = 0, j = 0, k = 0;
while(i <= n && j <= m)
{
if(a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}

while(i <= n)
c[k++] = a[i++];
while(j <= m)
c[k++] = a[j++];

Complexity will be O(n+m)

People read the question: Constant extra space, so no third array.

This is a tough problem and had been (solved now) the topic of research for years. Congrats if you get it in an interview. Go publish your solution, it will probably be the easiest solution to date.

Adobe interviewers suck for asking this question.

use heap mean array

int[] one = ...
int[] two = ...
int m = one.length;
int n = two.length;
int k;
while(i<m && j<n)
{
while(one[i] > two[j])
{
int t = one[i]; one[i] = two[j]; two[j] = t;
i++;
k = j;
while(k < n-1)
{
if(two[k] > two[k+1]
{
t = two[k]; two[k] = two[k+1]; two[k+1] = t;
break;
}
k++;

}
}
j++;
}

int[] one = ...
int[] two = ...
int m = one.length;       
int n = two.length;
int k;
while(i<m && j<n)
{
	while(one[i] > two[j])
	{
		int t = one[i]; one[i] = two[j]; two[j] = t;
		i++;
		k = j;
		while(k < n-1)
		{
			if(two[k] > two[k+1]
			{
				t = two[k]; two[k] = two[k+1]; two[k+1] = t;
				break;
			}
			k++;

		}
	}
	j++;
}

According to the problem , we need to merge both array into one of the ( which one is larger one ).

since we need to merge in one , then the problem will arise like insertion in middle of array. so we start comparing the both array from end ( as given both array are sorted ) we can acheive this in linear time with space constant

O(NM) //// N - Size of arr1 and M size of Arr2
////This program is a true in-place sort. Works as follows
//// Ithink it can also be improved.
//// After exec. arr1 concat arr2 will give u sorted array.
//// Compare a[0] and b[0] to decide who is arr1. smaller is arr1
int main()
{
int a[] = {12,23,89,124,312,350,410};
int b[] = {250};

merge(a,b,6,0);

for(int i=0; i<7; i++)
cout<<a[i]<< " ";
cout<<endl;
for(int i=0; i<1; i++)
cout<<b[i]<< " ";
getch();
return 0;
}

void merge(int* arr1, int* arr2, int n1, int n2)
{
if(arr2[n2] < arr1[n1] )
{
int* swap = arr1;
arr1 = arr2;
arr2 = swap;
int temp = n1;
n1 = n2;
n2 = temp;
}

int i = n1, j = n2-1;

while(j >=0)
{
if(arr1[i] > arr2[j])
{
int temp= arr1[i];
arr1[i] = arr2[j];
arr2[j] = temp;
bubble(arr1,i);

}
j--;
}

}

void bubble(int* arr1, int n)
{
while(arr1[n]< arr1[n-1] && n>= 1)
{
int temp = arr1[n];
arr1[n] = arr1[n-1];
arr1[n-1] = temp;
n--;
}
}

}}}

Very Good Solution Uttam....

Awesome solution Uttam well done !!

Uttam's solution doesn't meet the "minimum time complexity criterion". It has the same time complexity equivalent to the solution given by "concatenating the two arrays A and B, and then performing a heapsort". Linear time/Sublinear space algorithms, although very complicated to implement, exists for merging two arrays.

------------Thread closed-----------
solution is provided by Uttam