4

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);
            }
        }
    }
}
Leonardo Lopez
  • 1,113
  • 6
  • 20
  • 39
  • `that would make the time complexity larger than Big-O(N)` ... actually the best performance in general which can be achieved is roughly `O(N*lgN)`, which is _worse_ than `O(N)`. So having an initial `O(N)` operation where you bucket the three arrays in a single place most likely won't hurt the overall performance of your sort. – Tim Biegeleisen Jun 21 '16 at 03:45
  • Look into divide-and-conquer approaches like merge sort and quicksort. – Tim Biegeleisen Jun 21 '16 at 03:45
  • @TimBiegeleisen If I am able to make one pass thru each of the 3 arrays, assigning the lowest value to the final array (as in the implementation above), how would would the time complexity exceed O(N)? – Leonardo Lopez Jun 21 '16 at 03:51
  • Are the three arrays already sorted? If they are, then you might be able to do this in `O(N)`. In the general case this is no different from any other sorting problem. – Tim Biegeleisen Jun 21 '16 at 04:12
  • Best case of merging sorted arrays is O(n log k), where n is the total number of items, and k is the number of lists. For merging two arrays that works out to O(n * log(2)), which is the same as O(n). Your example is just the general priority queue based merge, hard coded with conditionals taking place of the explicit priority queue. Analysis will show that the number of comparisons in the worst case is O(n log k). – Jim Mischel Jun 21 '16 at 20:08
  • Did any of the answers resolve your question? Could you leave a comment or accept the answer of your choice? – trincot Jun 28 '16 at 11:28

5 Answers5

4

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.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • It's interesting to note that this code is really just an implementation of the standard priority queue based k-way merge, hard-coded for the case where k == 3. You'll note that the number of comparisons in the worst case is O(n log k), not O(n). – Jim Mischel Jun 21 '16 at 20:05
  • 4
    The number of comparisons is indeed *O(n logk)*, but since *k* is a constant in this question, we may rightly say it is *O(n)*. – trincot Jun 21 '16 at 20:15
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.

Community
  • 1
  • 1
Nicomak
  • 2,319
  • 1
  • 21
  • 23
  • @trincot I must have missed this, sorry. – Tim Biegeleisen Jun 21 '16 at 05:23
  • Sorry, but that's not O(n).If you extend your example to 5 arrays, you can easily see that you the complexity is greater than O(n). The first time you look at arrays `a` and `b`. Then you look at `ab` and `c`. Then `abc` and `d`, etc. Worst case complexity is O(k^2 * n), where `k` is the number of lists and `n` is the total number of items. Of course, if you say that `k` is constant, then, yeah, I suppose you could say that the algorithm is O(n). Also, even with three arrays, the number of comparisons you do depends on the order in which you merge the arrays. – Jim Mischel Jun 21 '16 at 19:57
  • I'm aware of that, but the question says "3 sorted arrays". I am not the one who decided that k is a constant. I think my solution is magnificent, and I think Dijkstra would have been impressed by it if he was still alive [troll face] – Nicomak Jun 22 '16 at 02:38
0

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,

mcdowella
  • 19,301
  • 2
  • 19
  • 25
0

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;
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61
0

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

Pranaya Ranjan Behera
  • 1
  • 1