CareerCup

Suppose you have the following inputs:
a[]
b[]
c[]
d[] // destination array of size 3*m
m // the size of each small array

1. Merge the two of the arrays and start placing in the destination array at index "m",
thus leaving space for "m" number of elements at the beginning of the array.
2. Now start merging the third array with the larger array in the destination array
located at position "m"

void merge(int a[], int b[], int c[], int d[], int m)
{
    int i = 0, j = 0, didx;
    
    // Merge the first two arrays into the largest starting at index "m"   
    didx = m; // destination index   
    while (i < m && j < m){
        if (a[i] <= b[j]) {
            d[didx] = a[i];
            ++i;
        }
        else {
            d[didx] = b[j];
            ++j;
        }    
        ++didx;
    }

    if (i < m) {
        while(i < m){
            d[didx] = a[i];
            ++didx;
            ++i;
        }
    }
    else {
        while(j < m){
            d[didx] = b[j];
            ++didx;
            ++j;
        }
    }

    // Now merge the last array into the destination
    // [0] .... [m] ...... [3*m - 1]
    i = 0;
    j = m;
    didx = 0;
    while (i < m && j < 3 * m) {
        if (c[i] <= d[j])
            d[didx++] = c[i++];
        else
            d[didx++] = d[j++];
    }

    // If there is a tail in first array, then copy it to the destination
    // otherwise the rest of the elements are in their proper positions
    while (i < m)
        d[didx++] = c[i++];
}

Use 4 pointers from the ends of the 3 sorted arrays as well as the larger array.
1. Use 3 way comparison to find out the maximum element of the 3 sorted arrays and place it at the end of the larger array. Decrement the pointer of the larger array and of the sorted array where the maximum was found.
2. Repeat step 1 until one of the array is exhausted.
3. Start doing 2-way comparison and placing the maximum value in the larger array
4. Repeat step 3 until only one array remains
5. Copy the contents of the remaining sorted array into the larger array.

public int[] threeWayMerge(int[] a, int[] b, int[] c) {
	if (a == null || b == null || c == null) {
		return null;
	}

	int[] res = new int[a.length + b.length + c.length];
	System.arraycopy(a, 0, res, 0, a.length);
	twoWayMerge(res, a.length, b);
	twoWayMerge(res, a.length + b.length, c);
	return res;
}

public void twoWayMerge(int[] large, int count, int[] small) {
	int p1 = count - 1;
	int p2 = small.length - 1;
	int last = count + small.length - 1;
	while (p1 >= 0 && p2 >= 0) {
		large[last--] = large[p1] > small[p2] ? large[p1--] : small[p2--];
	}
	if (p2 >= 0) {
		System.arraycopy(small, 0, large, 0, p2 + 1);
	}
}

Initialise the next element in each array as infinite. Then start merging the three arrays by finding the minimum number from particular indecis of three arrays and incrementing the index of array with minimum number

@ashot madatyan :.I did not understand 'Merge the two of the arrays and start placing in the destination array at index "m", thus leaving space for "m" number of elements at the beginning of the array' . Your solution is as good as merging arrays a[ ],b[ ] into d[ ] and then merging d[] with c[ ] . Please let me know if I am wrong