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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ** | |
| * Created with IntelliJ IDEA. | |
| * User: Ravi | |
| * Date: 3/20/14 | |
| * Time: 7:47 AM | |
| */ | |
| public class MergeSortedArrays { | |
| public static void main(String args[]) | |
| { | |
| int [] A = {1, 3, 5, 7, 9, 11, 13, 15, 0, 0, 0, 0, 0, 0, 0}; | |
| int [] B = {2, 4, 6, 8, 10, 12, 14}; | |
| mergeSortedArrays(A,8,B,7); | |
| for( int i = 0; i < A.length; i++ ) | |
| { | |
| System.out.print( A[i] + " "); | |
| } | |
| } | |
| public static void mergeSortedArrays(int[] A, int m, int[] B, int n) | |
| { | |
| int res = m+n-1; | |
| int i = m - 1,j = n - 1; | |
| while( i >= 0 && j >= 0 ) | |
| { | |
| if( A[i] > B[j] ) | |
| A[res--] = A[i--]; | |
| else | |
| A[res--] = B[j--]; | |
| } | |
| while( j >= 0 ) //move left over elements in B to A | |
| A[res--] = B[j--]; | |
| } | |
| } |
by