CareerCup

merge sort from right to left, placing the result in "a" as you go. return a.

Set two pointers at the very last number of the two arrays. Compare with the two numbers at the pointers, put the bigger one at the end of first array and move that pointer one left. Continue this process until both pointer move at the head of the arrays.

public static void main(String[] args)
{
	int[] arr1=new int[]{7,10,11,20,0,0,0}//0 at the end should be assumed as empty space
	int arr2 = new int[]{1,3,7};
	
	int i2=arr2.length() -1;
	int i1 = arr1.length()  -1 - i2;
	int j = arr1.length()-1;

	while(i1>0 && i2 > 0 && j > 0)
	{
		if(arr1[i1] > arr2[i2])  
			 arr[j--] = arr[i1--];
		else
			 arr[j--] = arr[i2--];
	}

	if(i2>=0)
	{
		while(i2>=0)
		{
			arr[j--] = arr[i2--]
		}
	}

	if(i1>=0)
	{
		while(i1>=0)
		{
			arr[j--] = arr[i1--]
		}
	}


}

/*
a[] is the bigger array; 
b[] is the smaller array; 
n is the size of bigger array;
m is the size of smaller array
*/
merge(int a[], int b[], int n, int m)
{
	int c[n];
	int i = n-m-1;
	int j = m-1;
	int k = n-1;
	while(i>=0 && j>=0 && k>=0)
	{
		if(a[i] > b[j])
		{
			c[k] = a[i];
			i--;
		}
		else
		{
			c[k] = b[j];
			j--;
		}
		k--;
	}
	if(i<0)
	{
		while(j>=0 && k>=0)
		{
			c[k] = b[j];
			k--;
			j--;
		}
	}
	else if(j<0)
	{
		while(i>=0 && k>=0)
		{
			c[k] = a[i];
			k--;
			i--;
		}
	}
}

public int[] mergeSortedArray(int[] array1, int sizeA, int[] array2)
{
int i=sizeA;
int j = array2.length-1;
int k = array1.length -1;

while(k>=0 && i>=0 && j>=0)
{
if(array1[i] > array2[j])
{
array1[k]=array1[i];
k--;
i--;
}
else
{
if(j>=0)
{
array1[k]=array2[j];
}
k--;
j--;
}

}
return array1;
}

The empty space in a is equal to the number of element in b, so we can merge from last element without extra space.

void mergeSortAB(int *a, int *b)
{
	int ia = 3;
	int ib = 2;
	int last = 6;

	while (ib >= 0)
	{
		if (ia >= 0 && a[ia] > b[ib])
		{
			a[last--] = a[ia--];
		}
		else
		{
			a[last--] = b[ib--];
		}
	}
}

static int a[7] = {4, 10, 11, 20, 0, 0, 0};
static int a_len = 4;
static int b[3] = {1, 3, 7};

void merge_sort()
{
int store_pos = 6;
int a_cur = a_len-1;
int b_cur = 2;
while(a_cur >= 0 && b_cur >= 0) {
if (a[a_cur] > b[b_cur]) {
a[store_pos--] = a[a_cur--];
} else {
a[store_pos--] = b[b_cur--];
}
}

if (a_cur < 0) {
memmove(a, b, (b_cur+1)*sizeof(int));
}
}

pos is the positon of largest element in longarray
j is the positon of largest element in small arry i.e. size

int main()
{

int longarr[7] = { 4,10,11,20 };
int smallarr[3]= { 1,3,7 };


int i =0,pos=3, n=7, j=2;


while(j>=0  && pos >=0)
{
	if ( longarr[pos] > smallarr[j])
	{	
		longarr[--n] = longarr[pos];
		pos--;
	}
	else
	{
	longarr[--n] = smallarr[j];
	j--;
	}
}

if(pos < 0)
{
	while( j>=0)
	longarr[j--]=smallarr[j];
}

for(int k=0;k<7;k++)
cout<<longarr[k]<<"\t";

return 0;
}

What is mean by empty, it will initialized value or garbage value. Please clarify.

Merge and then sort :
int a[] = {4, 10, 11, 20, 0, 0, 0};
int b[] = {1,3,7};
int c = a.length+b.length;
int d[] = new int[c];
int num = 0;
for(int i=0;i<a.length;i++){
d[num] = a[i];
num++;
}

for(int j=0;j<b.length;j++){
d[num] = b[j];
num++;
}


for(int i=0;i<d.length;i++){
int temp=0;
for(int j=0;j<d.length-1;j++){
if(d[j]>d[j+1]){
temp = d[j];
d[j] = d[j+1];
d[j+1] = temp;

}
}

}

for(int k=0;k<d.length;k++){
System.out.print(d[k] + " ");
}

a = [4, 10, 11, 20] 
b = [1,3,7]

count = 0
for num in b:
    while True:
        if num < a[count]:
            a.insert(count, num)
            count +=1
            break;
        count +=1
print a


OUTPUT:
[1, 3, 4, 7, 10, 11, 20]

int[] big = new int[] {4,10,11,20,0,0,0};
		int[] small = new int[] {1,3,7};
		int smallLength = small.length -1 ;
		int bigvalue = big.length -1 -smallLength-1;
		int bigLength = big.length -1;
		
		while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
		if(small[smallLength]>big[bigvalue]){
			big[bigLength] = small[smallLength];
			bigLength--;
			smallLength--;
		}
		
		else if (big[bigvalue]>small[smallLength]){
			
			big[bigLength] = big[bigvalue];
			bigLength--;
			bigvalue--;
		}
		
		if (smallLength>=0){
			while(smallLength>=0){
				if(small[smallLength]<big[bigLength]){
					big[bigLength] = small[smallLength];
				}
				smallLength--;
				bigLength--;
				
				
			}

}

int[] big = new int[] {4,10,11,20,0,0,0};
		int[] small = new int[] {1,3,7};
		int smallLength = small.length -1 ;
		int bigvalue = big.length -1 -smallLength-1;
		int bigLength = big.length -1;
		
		while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
		if(small[smallLength]>big[bigvalue]){
			big[bigLength] = small[smallLength];
			bigLength--;
			smallLength--;
		}
		
		else if (big[bigvalue]>small[smallLength]){
			
			big[bigLength] = big[bigvalue];
			bigLength--;
			bigvalue--;
		}
		
		if (smallLength>=0){
			while(smallLength>=0){
				if(small[smallLength]<big[bigLength]){
					big[bigLength] = small[smallLength];
				}
				smallLength--;
				bigLength--;
				
				
			}

}

int[] big = new int[] {4,10,11,20,0,0,0};
		int[] small = new int[] {1,3,7};
		int smallLength = small.length -1 ;
		int bigvalue = big.length -1 -smallLength-1;
		int bigLength = big.length -1;
		
		while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
		if(small[smallLength]>big[bigvalue]){
			big[bigLength] = small[smallLength];
			bigLength--;
			smallLength--;
		}
		
		else if (big[bigvalue]>small[smallLength]){
			
			big[bigLength] = big[bigvalue];
			bigLength--;
			bigvalue--;
		}
		
		if (smallLength>=0){
			while(smallLength>=0){
				if(small[smallLength]<big[bigLength]){
					big[bigLength] = small[smallLength];
				}
				smallLength--;
				bigLength--;

}

int[] big = new int[] {4,10,11,20,0,0,0};
		int[] small = new int[] {1,3,7};
		int smallLength = small.length -1 ;
		int bigvalue = big.length -1 -smallLength-1;
		int bigLength = big.length -1;
		
		while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
		if(small[smallLength]>big[bigvalue]){
			big[bigLength] = small[smallLength];
			bigLength--;
			smallLength--;
		}
		
		else if (big[bigvalue]>small[smallLength]){
			
			big[bigLength] = big[bigvalue];
			bigLength--;
			bigvalue--;
		}
		
		if (smallLength>=0){
			while(smallLength>=0){
				if(small[smallLength]<big[bigLength]){
					big[bigLength] = small[smallLength];
				}
				smallLength--;
				bigLength--;

}

int[] big = new int[] {4,10,11,20,0,0,0};
		int[] small = new int[] {1,3,7};
		int smallLength = small.length -1 ;
		int bigvalue = big.length -1 -smallLength-1;
		int bigLength = big.length -1;
		
		while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
		if(small[smallLength]>big[bigvalue]){
			big[bigLength] = small[smallLength];
			bigLength--;
			smallLength--;
		}
		
		else if (big[bigvalue]>small[smallLength]){
			
			big[bigLength] = big[bigvalue];
			bigLength--;
			bigvalue--;
		}
		
		if (smallLength>=0){
			while(smallLength>=0){
				if(small[smallLength]<big[bigLength]){
					big[bigLength] = small[smallLength];
				}
				smallLength--;
				bigLength--;			
				
			}

int[] big = new int[] {4,10,11,20,0,0,0};
		int[] small = new int[] {1,3,7};
		int smallLength = small.length -1 ;
		int bigvalue = big.length -1 -smallLength-1;
		int bigLength = big.length -1;
		
		while( bigLength>=0 && smallLength>=0 && bigvalue>=0 )
		if(small[smallLength]>big[bigvalue]){
			big[bigLength] = small[smallLength];
			bigLength--;
			smallLength--;
		}
		
		else if (big[bigvalue]>small[smallLength]){
			
			big[bigLength] = big[bigvalue];
			bigLength--;
			bigvalue--;
		}
		
		if (smallLength>=0){
			while(smallLength>=0){
				if(small[smallLength]<big[bigLength]){
					big[bigLength] = small[smallLength];
				}
				smallLength--;
				bigLength--;			
				
			}

def merge_arr(a1,a2):
    a = []
    a = a1+a2
    return sorted(a)

            
                
    

print merge_arr([4,10,11,12],[1,3,2,4])

public class MergeNew {
	
	static int[] merge(int[] a, int[] b) {
		int i= a.length-4 ;
		int k = a.length-1;
		int j = b.length-1;
		while( i != -1 && j != -1) {
			if(a[i] > b[j]) {
				a[k] = a[i]; 
				i--;
			} else {
				a[k] = b[j];
				j--;
			}
			k--;
		}
		
		while(i != -1) {
			a[k] = a[i];
			i--;
			k--;
		}
		
		while(j != -1) {
			a[k] = b[j];
			j--;
			k--;
		}
		return a;
	}
	
	public static void main(String[] args) {
		
		int a[] = {4, 10, 11, 20, 0, 0, 0}; 
		int b[] = {1,3,7};
		
		int[] c = (merge(a,b));
		
		for(int k : c) {
			System.out.print(k + " ");
		}
		
	}

}

Are we allowed to use O(1) extra space?