Saturday, February 16, 2013

Merge Two Sorted Arrays



/*
 * Question:
   Given two sorted arrays A1 and A2, of lengths L1 and L2 , L1 < L2 and the last L1
   slots in A2 are vacant, get me all the numbers in A2, sorted in the most efficient
   manner without using extra space.
 
 * Solution:  
 * (Same question can be asked for merging more than 2 arrays
 *  follow the same pattern by merging 1 array with main array at a time)
 *
 *  Run a for loop from end of A2 and compare A1 and A2 from their ends.
 *
 *  Runtime: O(n);
 *  Space time: O(1);
 */
public class MergeTwoSortedArrays {

private int[] A1;
private int[] A2;

public MergeTwoSortedArrays() {
A1 = new int[4];
A2 = new int[10];

A1[0]= 2;
A1[1]= 4;
A1[2]= 7;
A1[3]= 9;

A2[0]= 1;
A2[1]= 3;
A2[2]= 5;
A2[3]= 6;
A2[4]= 8;
A2[5]= 10;
}

public void mergeTwoArrays(){

int l2 = 5;
int l1 = 3;
for(int i = A2.length-1; i>=0; i--) {

if(l1 >=0) {
if(A2[l2] > A1[l1]) {
A2[i] = A2[l2];
l2--;
}
else {
A2[i] = A1[l1];
l1--;
}
}
else {
break;
}
}
}

public void display() {

for(int i=0; i System.out.print(A2[i]+" ");
}
}

public static void main(String args[]) {

MergeTwoSortedArrays obj = new MergeTwoSortedArrays();

obj.mergeTwoArrays();
obj.display();
}
}


No comments: