July 31, 2011

# Combining and Merging Two Arrays

**Merging Two Arrays Problem**

Given two sorted arrays A and B of different sizes m and n. Describe an algorithm to combine the two arrays into one array. The output array must not have duplicates. The output array must maintain the original order of values in A and B

**Solution**

If you recall the well known merge sort algorithm then this problem is nothing but the last step in merge sort. Merge sort is a divide and conquer algorithm. It divides the input array into two halves then sort each half and at the end it merges the two halves into one sorted array in linear time. The overall running time of merge sort is nlogn. Please refer to this post for more information about merging two arrays.