Merge two sorted arrays in Java

Problem

Let’s understand the problem. We have two sorted arrays and we would like to merge them into one.

Algorithm

This algorithm is part of merge sort algorithm.

1. Let’s say we have two sorted array A and B. We need to create another array of size [A] + size[B]
2. Let’s maintain 3 pointers
   • i, which will point to left array
   Advertisement
   • j, which will point to right array
   • k, which will point to resultant array
3. Now will initialise i, j, k = 0;
4. We start by comparing the elements in both the arrays, and we pick the smaller one.
5. We increase pointer of smaller one and resultant array.

Code

public static int[] merge(int[] foo, int[] bar) {

    int fooLength = foo.length;
    int barLength = bar.length;

    int[] merged = new int[fooLength + barLength];

    int fooPosition, barPosition, mergedPosition;
    fooPosition = barPosition = mergedPosition = 0;

    while(fooPosition < fooLength && barPosition < barLength) {
        if (foo[fooPosition] < bar[barPosition]) {
            merged[mergedPosition++] = foo[fooPosition++];
        } else {
            merged[mergedPosition++] = bar[barPosition++];
        }
    }

    while (fooPosition < fooLength) {
        merged[mergedPosition++] = foo[fooPosition++];
    }

    while (barPosition < barLength) {
        merged[mergedPosition++] = bar[barPosition++];
    }

    return merged;
}