Saturday, March 20, 2010

Merging two sorted arrays

Q.Write a method that will take two sorted arrays as input and merge them and give a new sorted array as output.

Soln:- Take the two arrays straight go to the ends (I assume you consider checks for boundary conditions) cause in this approach you also handle the case that you are not allowed to use extra space with the condition that one of the array has extra space left to accommodate the other.
Start from the tail picking and comparing each element and putting the largest among them to the tail of new array. Decrement the index of the array of which a value is put in the new array. Repeat until all elements are traversed.

Code:

int[] MergeSortedArrays(int[] array1, int[] array2)
{
int indexArray1 = array1.length - 1;
int indexarray2 = array2.length - 1;


if(array1 == null || array1.length == 0)
return array2;
else if(array2 == null || array2.length == 0)
return array1;

int[] mergedArray = new int[array1.length + array2.length];


for(int indexDestination = indexArray1 + indexarray2 + 1;indexDestination>=0;indexDestination--)
{
if(array1[idexArray1] > array2[indexarray2])
{
mergedArray[indexDestination] =array1[indexArray1];
idexArray1--;
}
else
{
mergedArray[indexDestination] = array2[indexarray2];
indexarray2--;
}
}

return mergedArray;
}

Time complexity of this algorithm would be O(n) where n is the sum total of number of elements in both the arrays, with extra space complexity of O(n) which actually is the requirement

No comments:

Post a Comment