How to merge 3 sorted arrays into 1 sorted array in Big-O(N) time?

Trying to merge 3 arrays into one so that the final array is in order.

Given

int[] a = {1,3};
int[] b = {2,4};
int[] c = {1,5};

Merge the arrays so that the final array d = {1,1,2,3,4,5}

Can’t just concatenate them and then sort the d array because that would make the time complexity larger than Big-O(N).

This is what I got so far. Having problems with indexes out of bound exceptions:

public static void main(String[] args) {
    // Sort these 3 arrays. The final array should be d = {1,1,2,3,4,5}
    int[] a = {1,3};
    int[] b = {2,4};
    int[] c = {1,5};
    int[] d = new int[a.length + b.length + c.length];

    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;

    for (int iteration = 0; iteration <= d.length; iteration++){
        if ((i != a.length || j != b.length) && a[i] < b[j]){
            if (a[i] < c[k]){
                // then a[i] is smallest
                d[l] = a[i];
                i++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (a[i] > c[k]){
                // then c[k] is smallest
                d[l] = c[k];
                k++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (a[i] == c[k]){
                d[l] = a[i];
                i++;
                l++;
                d[l] = c[k];
                k++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
        }
        else if(b[j] < a[i]){
            if (b[j] < c[k]){
                // b[j] is smallest
                d[l] = b[j];
                l++;
                j++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (b[j] > c[k]){
                // c[k] is smallest
                d[l] = c[k];
                l++;
                k++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
            else if (b[j] == c[k]){
                d[l] = b[j];
                j++;
                l++;
                d[l] = c[k];
                k++;
                l++;
                displayArrayContents(a,b,c,d,i,j,k,l);
            }
        }
    }
}

Answer

Your idea is correct and represents a O(n) solution. However, there are indeed some issues in your code, some of which will lead to out-of-bound exceptions:

• You access c[k] without first making sure that k < c.length;
• Even when you do test on length, you do it in a way that does not avoid such invalid access: (i != a.length || j != b.length) && a[i] < b[j] will still result in a[i] being accessed when i === a.length (notably when j != b.length);
• The number of times the outer loop needs to iterate will often be wrong because sometimes (in case of equality) you store two values in the target array, which makes the array fill up faster than your loop foresees. In fact, the case of equality (like a[i] == c[k]) does not really need to be treated separately. If you treat it together with > (so: >=) the algorithm is still correct: the second (equal) value will be copied in the next iteration then;
• Even if you fix the previous issue, your outer loop still makes one iteration too many; the for condition should be < d.length instead of <= d.length

Not problematic, but you have a lot of duplication in your code:

• You could move the call to displayArrayContents(a,b,c,d,i,j,k,l); outside of the if construct, so it is always executed, which is what you really want;
• As you always assign to d in the if construct, you could put that assignment “outside of the if” by using the ternary operator ? ... :;
• Although tests like i != a.length work for the intended purpose, it is good practice to test like this: i < a.length.

Here is the code with the above taken into account:

import java.util.Arrays; // for easy output of arrays with Arrays.toString().

class Main {
  public static void main(String[] args) {
    // Sort these 3 arrays. The final array should be d = {1,1,2,3,4,5}
    int[] a = {1,3};
    int[] b = {2,4};
    int[] c = {1,5};
    int[] d = new int[a.length + b.length + c.length];

    int i = 0;
    int j = 0;
    int k = 0;
    for (int l = 0; l < d.length; l++) {
      d[l] = i < a.length && (j >= b.length || a[i] < b[j])
                ? (k >= c.length || a[i] < c[k]
                    ? a[i++]
                    : c[k++])
                : (j < b.length && (k >= c.length || b[j] < c[k])
                    ? b[j++]
                    : c[k++]);
       // Uncomment this if you still need it:
       //displayArrayContents(a,b,c,d,i,j,k,l); 
    }

    System.out.println(Arrays.toString(d));
  }
}

Output of last statement:

[1, 1, 2, 3, 4, 5]

See it run on repl.it.