How to merge 3 sorted arrays into 1 sorted array in Big-O(N) time?
<p>Trying to merge 3 arrays into one so that the final array is in order. </p>

<p>Given </p>

<pre><code>int[] a = {1,3};
int[] b = {2,4};
int[] c = {1,5};
</code></pre>

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

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

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

<pre><code>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 &lt;= d.length; iteration++){
        if ((i != a.length || j != b.length) &amp;&amp; a[i] &lt; b[j]){
            if (a[i] &lt; 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] &gt; 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] &lt; a[i]){
            if (b[j] &lt; 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] &gt; 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);
            }
        }
    }
}
</code></pre>