CareerCup

This is a variation to question 9626448.

ok
just take two integers i and j which points to last index of array wher value exist means
at n-1
and j should be also n-1
k should be assined as 2*n-1
now start compairing value at these if b[i]>a[j] then just do b[k--]=b[i--];
in else
do b[k--]=a[j--];
do till u not have k!=0

Copy b's elements to the second half of b. Now just merge on b.

bubble up the vacant spaces to the end, and start merging from the end of arrays.

can we use extra space?

<pre lang="" line="1" title="CodeMonkey39953" class="run-this">#include<stdio.h>
#include<conio.h>

int main()
{
int a[5],b[10],i,j,n=5,k;

printf("a :");
for(i=0;i<5;i++)
scanf("%d",&a[i]);
printf("b :");
for(i=0;i<5;i++)
scanf("%d",&b[i]);


for(i=0,j=0;i<n && j<n;)
{
if(a[i]<b[j])
{
for(k=n-1;k>=j;k--)
b[k+1]=b[k];
b[k+1]=a[i];
i++;
j++;
n+=1;
}
else
j++;
}
for(i=0;i<n;i++)
printf("%d ",b[i]);
getch();
return 0;
}


</pre>

O(n) is easily possible.

A[2n] shift all elements to A[n] making A[n+1] A[2n] vacant and then merge.

Two loops O(2n) + O(2n) = O(n)... Wondering if can be done in less.

first put all the elements in b[] to the left most side or the array leaving n spaces empty on the right. O(n) use 2 pointers..
then start the pointers from a[n-1] and b[n-1] and another pointer where you will be filling either of these 2 depending which is bigger. this pointer will be at b[2n-1]. O(n) for a[] and O(n) for b[].. therefore O(3n) = O(n)

1. Move all elements in big array to end keeping order same in O(n+n)
2. Merge 2 sorted contiguous arrays in big array. index1 = 0 index2 = n: O(m+n)

ME()
	k = m+n-1
	for each i from 0 to m+n-1
		if(b[i] != -1)
			swap(i,k)
			k--

M()
	i = 0
	j = n
	k = 0
	while(i < n ||  j< n+m)
		if(s[i] <= b[j])
			b[k++] = s[i++]
		else
			b[k++] = b[j++]
	if(j < (m+n))
		while(j < (m+n))
			b[k++] = s[j++]
		

MA()
	ME(b)
	M()