Merge two sorted arrays algorithm (Java)

Tags: , ,

Given two sorted arrays or lists, how to merge them into a sorted array?  

This is a fundamental problem as it is a common requirement to merge two sorted arrays into one sorted array. The algorithm of merging two sorted arrays is also the basics of the one of the most famous sort algorithms: merge sort.

Suppose there are two sorted arrays A and B, and we want to merge them into a third Array C.

We define three indexes a, b, c, which points to the beginning of the three arrays A, B, and C respectively. 

Now we compare A[a] with B[b] when a < A.length and b < B.length.

if A[a] <= B[b], we assign A[a] to C[c], and increase both a and c by 1. 

if A[a] > B[b], we assign B[b] to C[c], and increase both b and c by 1. 

We also need to handle the case such as when all the elements in one array (e.g. A) has been processed but the other array (e.g., B) still has elements left. In this case, we just copy the remaining elements from B into C.

The following code implements the merge sorted arrays algorithm in Java: