CareerCup

Using merge sort? O(n)

public static int[] merge(int[] a, int[] b) {

int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
if (a[i] < b[j])
{
answer[k] = a[i];
i++;
}
else
{
answer[k] = b[j];
j++;
}
k++;
}

while (i < a.length)
{
answer[k] = a[i];
i++;
k++;
}

while (j < b.length)
{
answer[k] = b[j];
j++;
k++;
}

return answer;
}

public class MergeSorted {
public static void main(String[] args) {

int[] arr1 = { 1, 2, 12, 33, 35, 36 };
int[] arr2 = { 13, 20, 40, 60 };

int[] arr3 = new int[arr1.length + arr2.length];

int i, j, x = 0;
for (i = 0, j = 0; i < arr1.length && j < arr2.length;) {
System.out.println("i: " + i + " j: " + j);

if (arr1[i] < arr2[j])
arr3[x++] = arr1[i++];
else
arr3[x++] = arr2[j++];
}

while (i < arr1.length)
arr3[x++] = arr1[i++];

while (j < arr2.length)
arr3[x++] = arr2[j++];

for (int z : arr3) {
System.out.println(z);
}

}
}

public class MergeArrays {

	public static int[] merge(int[] a, int[] b) {
		int length = a.length + b.length;
		int[] c = new int[length];
		
		int i=0, j=0, k=0;
		
		while(k< c.length) {
			
			if(i == a.length) {
				c[k] = b[j++];
			} else if(j == b.length) {
				c[k] = a[i++];
			} else if(a[i] < b[j]) {
				c[k] = a[i++];
			} else {
				c[k] = b[j++];
			}
			++k;
		}
	
		return c;
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] a = {1,3,7,9,11};
		int[] b = {2,4,6,7,22};
		
		int[] c = merge(a,b);
		for(int num : c) {
			System.out.print(num + " ");
		}
		
	}
	
}

1. i =0, j =0, k=0. compare a[i] and b[j], put the one that is less in the result[k].
2. increment the index of array, at whieh the element was less and increment k.
3. repeat above steps till both arrays are exhausted, or if one of them is exhausted, write values from other array to result directly.

here's a javascript version. concat arrays first, then use the native sort function with ascending pattern

var array1 = [1, 2, 3, 4, 5, 6, 7 ];
    var array2 = [1, 2, 4, 4, 4, 4, 4, 12, 22];
    
    function asc(a, b){
      return a - b;
    }
    
    function merge(arr1, arr2){
      return arr1.concat(arr2).sort(asc);
    }
    
    console.log(merge(array1, array2));

Need to use two stacks.
1) Put these two arrays in these stacks.
2) Create an array of size Size of A1 + Since of A2
3) Pop Stack 1 and Pop Stack 2
4) If Pop Stack < Pop Stack 2, pop Stack 1 goes into Array. Else pop Stack 2.
5) Keep popping the stacks till its empty.

Apply merge sort

def merge(L1, L2):
    p = q = 0
    L = []
    while not (p == len(L1) and q == len(L2)):
        if p == len(L1):
            L.append(L2[q])
            q += 1
        elif q == len(L2):
            L.append(L1[p])
            p += 1
        else:
            if L1[p] < L2[q]:
                L.append(L1[p])
                p += 1
            else:
                L.append(L2[q])
                q += 1
    return L

L1 = input()
L2 = input()
print merge(L1, L2)

public class Merge {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int [] a = {1, 3, 5, 7, 9, 11};
		int [] b = {2, 4, 6, 6, 8, 10};
		for(int i : merge(a, b))
			System.out.print(i + ", ");
		System.out.println();
		
	}
	
	public static int [] merge(int [] a, int [] b)
	{
		int [] arr = new int[a.length + b.length];
		int aAt = 0;
		int bAt = 0;
	//	int at = 0;
		
		while(aAt < a.length && bAt < b.length)
		{
			if(a[aAt] < b[bAt])
			{
				arr[aAt + bAt] = a[aAt];
				aAt++;
			}
			else
			{
				arr[aAt + bAt] = b[bAt];
				bAt++;					
			}
		}
		for(int i = aAt; i < a.length; i++)
		{
			arr[aAt + bAt] = a[aAt];
			aAt++;
		}
		for(int i = bAt; i < b.length; i++)
		{
			arr[aAt + bAt] = b[bAt];
			bAt++;				
		}

		return arr;
	}

}

Simply use the 'merge' part of a merge sort.
en.wikipedia.org/wiki/Merge_sort

one array should have enough space in the end to hold another array

array 1 {1,3,5,7,9,,,,,}
array 2 {2,4,6,8,10}

1. traverse array 1 to find the last element say 9 in this case
2. compare the last element of both the array's and start filling array1 from the end
3. based on from which array we take the element, decrement the index till all the elements from array 2 goes to array1

void print_arr(int *arr,int size);
int main()
{
int arr1[]= {23,85,100,207,217};
int arr2[] ={78,83,90,102,105} ;
int arr3[10] ={};
int arr1_index =0,arr2_index =0;

for(int i =0; i< 10;i++)
{
if(arr1[arr1_index] < arr2[arr2_index])
{
arr3[i]= arr1[arr1_index];
arr1_index++;
}
else
{
arr3[i] = arr2[arr2_index];
arr2_index++;
}
}
print_arr(arr3,10);
return 0;
}
void print_arr(int* arr,int size)
{
for(int i =0;i<size;i++)
std::cout << arr[i]<< std::endl;
}

methodName(){
int[] first = {3,6,8,12,30};
int[] second = {5,9,14,50};

int size = first.length;// + second.length;
int temp = second.length;

int small=0;
int[] join = null;
if(first.length < second.length){
size = second.length;
temp = first.length;
}

for(int outer=0; outer <size; outer++){
for(int inner=small; inner<temp; inner++){
if(first[outer] < second[inner]){
System.out.print(" " + first[outer]);
break;
}else{
System.out.print(" " + second[inner]);
small++;
}
}
}
}

Die.