Thursday, March 20, 2014

Merging two sorted arrays

Given two sorted arrays A, B of lengths m, n respectively. How to merge them into a single sorted array?. Let us assume that A has sufficient space (m+n) for result array.

For example let A = [1, 3, 5, 7, 9], and B = [2, 4, 6, 8, 10]. The function should return A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as a result.

Since the array A has sufficient space for the merged array, we can start from the end of the array A and start filling the result elements.

We compare the elements at i and j indices. We move the bigger element to the end pointed by res and decrement the corresponding index. We do this until we reach the beginning of any array. Finally we check if there any left over elements in the second array. If there are, we have to move them to the first array.