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

Question

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 1

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.

Answer 2

Follow these steps:

• Get the answer code from here: How to merge two sorted arrays into a sorted array?
• Call that function on a and b, to get the resulting array ab
• Call that function on ab and c, to get your result abc
• You've called an O(n) function twice, so it's still O(n). BOOM.

The truth is, playing around with array indices is frustrating. If you can get those arrays as Queues or Itererators instead, just take() or next() the smallest value in each iteration and put it in the result list, it will be a lot cleaner.

Answer 3

You need to be clear on what changes with N. If you always have just three arrays and their size, or maximum size, changes with N, then almost any code which repeatedly selects the smallest number available from any of the three arrays, removes it, and appends it to the end of the result array, will be O(N). Your code for selecting the smallest number might be clumsy and expensive, but it is just a constant factor which does not change as N increases.

If the number of arrays to merge increases with N then you need to be more careful about how you select the smallest number available, and you will eventually end up with a sorting problem, which you can't do in linear time under the usual assumptions.

Typically external sorting will merge a large number of lists held on disk using a heap (e.g. http://www.geeksforgeeks.org/external-sorting/). This will be more efficient for merging a large number of lists at a time, but just gains you a constant factor,

Answer 4

Assuming this is java, array names are references to arrays and can be swapped like pointers in C / C++. This can be used to reduce the number of conditionals in the main merge loop, making the code a bit simpler, but at the cost of swapping. Empty array checks are done before the main merge loop. This method can be easily expanded to handle a 4 way or greater merge, which would otherwise require a lot of conditionals.

static int[] Merge(int[] a, int[] b, int[] c)
{
    int[] d = new int[a.length + b.length + c.length];
    int[] e;   // temp used for swap
    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;
    int t;
    // empty array checks
    if(0 == b.length){      // if b empty
        if(0 == c.length){  // if b and c empty
            c = a;          //   c = a
            a = b;          //   a = b = empty
        } else {            // if b empty, c not empty
            e = a;          //   swap a and b
            a = b;
            b = e;
        }
    } else {                // else b not empty
        if(0 == c.length){  // if c empty
            e = c;
            c = b;          //   shift c = b, b = a
            b = a;
            a = e;          //   a = empty
        }
    }
    // main merge loop
    while(i < a.length){    // 3 way merge
        if(a[i] > b[j]){    // if b smaller swap
            e = a;
            a = b;
            b = e;
            t = i;
            i = j;
            j = t;
        }
        if(a[i] > c[k]){    // if c smaller swap
            e = a;
            a = c;
            c = e;
            t = i;
            i = k;
            k = t;
        }
        d[l++] = a[i++];
    }
    while(j < b.length){    // 2 way merge
        if(b[j] > c[k]){    // if c smaller swap
            e = b;
            b = c;
            c = e;
            t = j;
            j = k;
            k = t;
        }
        d[l++] = b[j++];
    }
    while(k < c.length)     // copy rest of c
        d[l++] = c[k++];
    return d;
}

Answer 5

Check this if logic looks simple to you.
Logic: Identify the smallest element from 3 arrays and add it in mergeArray. Also handle if all elements of array is covered( added in mergedArray), i.e. ignore that array from smallest number calculation.

import java.util.Arrays;

public class SortingAlgo {


    public static void main(String[] args) {

        int[] arr1 = {1,4,7,12,15,16,19,26,26, 29,35};
        int[] arr2 = { 3,8,12,14,40, 44, 45};
        int[] arr3 = {2,4,29, 30};


        int[] merged = getMerged(arr1, arr2, arr3);

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

  

    private static int[] getMerged(int[] arr1, int[] arr2, int[] arr3) {
        int[] merged = new int[ arr1.length + arr2.length + arr3.length];

        int i = 0; // Merged index
        int i1 = 0, i2=0, i3=0; // for arr1, arr2, arr3
        boolean i1Completed = false, i2Completed = false, i3Completed = false;

        while(i1 < arr1.length || i2 < arr2.length || i3 < arr3.length) {
            if(!i1Completed && (i2Completed || arr1[i1] <= arr2[i2]) &&  (i3Completed || arr1[i1] <= arr3[i3]  )){
                merged[i++] = arr1[i1++];  // arr1 element smallest
                if(i1 == arr1.length)
                    i1Completed = true;

            } else if(!i2Completed && (i1Completed || arr2[i2] <= arr1[i1] ) &&  ( i3Completed || arr2[i2] <= arr3[i3]) ){
                merged[i++] = arr2[i2++];

                if(i2 == arr2.length)
                    i2Completed = true;

            } else if(!i3Completed && ( i2Completed ||  arr3[i3] <= arr2[i2] ) && ( i1Completed ||  arr3[i3] <= arr1[i1]) ){
                merged[i++] = arr3[i3++];

                if(i3 == arr3.length)
                    i3Completed = true;

            }

        }
        return merged;
    }

}

Output: [1, 2, 3, 4, 4, 7, 8, 12, 12, 14, 15, 16, 19, 26, 26, 29, 29, 30, 35, 40, 44, 45]

check output at replit