Matt Matt - 3 months ago 25
Java Question

Naive way to merge k arrays

I'm trying to implement an algorithm to merge k sorted arrays (each with n elements) in a naive way deliberately:

Steps:


  1. merge the first and second arrays

  2. merge the above resulting array with the 3rd array

  3. merge the above resulting array with the 4th array

  4. ... and so on until merge with the k th array



My code can output the sorted single array for 3x3, 4x4, 5x5 2D arrays, but the it stucks when the 2D array become 6x6.

Is it because the complexity of the code is too bad that it take too long to compile? Or there are some silly logical errors that I am not aware of?

I read through my code and what I guess the problem is the line I marked with "<<<==== ??". How can I make it right?

public class Merge {

// merge 2 arrays into a single sorted array
private static int[] merge(int[] arrayA, int[] arrayB) {
int n1 = arrayA.length; // number of elements in arrayA
int n2 = arrayB.length; // number of elements in arrayB
int[] mergeArray = new int[n1+n2];

int i = 0; // pointer of current index in mergeArray
int p1 = 0; // pointer of current index in arrayA
int p2 = 0; // pointer of current index in arrayB
while (p1 < n1 && p2 < n2) {
// put the lowest number the mergeArray until one of the array is done
if (arrayA[p1] < arrayB[p2]) {
mergeArray[i] = arrayA[p1];
i++;
p1++;
}
else if (arrayB[p2] < arrayA[p1]) {
mergeArray[i] = arrayB[p2];
i++;
p2++;
}
}
// if all elements of arrayA is copied to mergeArray, then copy remaining elements in arrayB to it
if (p1 >= n1) {
for (int j = p2; j < arrayB.length; j++) {
mergeArray[i] = arrayB[j];
i++;
}
}
// if all elements of arrayB is copied to mergeArray, then copy remaining elements in arrayA to it
if (p2 >= n2) {
for (int j = p1; j < arrayA.length; j++) {
mergeArray[i] = arrayA[j];
i++;
}
}
return mergeArray;
}

public static int[] naiveMerge(int[][] data) {
int k = data.length; // number of sorted array
int n = data[0].length; // number of elements in each array
int[] resultArray = new int[k*n];

int[] tempArray = Merge.merge(data[0], data[1]); // merge the first two arrays
for (int i = 2; i < k; i++) {
// then merge in the third, fourth ... k arrays
tempArray = Merge.merge(tempArray, data[i]); // <<<==== ??
resultArray = tempArray;
}
return resultArray;
}

public static void main(String[] args) {

for (int c = 3; c <= 10; c++) {
int k = c;
int n = c;

int[][] data = new int[k][n];
// populates the 2D array with random number (0-99)
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
data[i][j] = new Random().nextInt(100);
}
}
// sort each row of array in the 2D array
for (int[] row : data) {
Arrays.sort(row);
}
System.out.println("Before merging:");
for (int[] row : data) {
System.out.println(Arrays.toString(row));
}
System.out.println("After merging:");
System.out.println(Arrays.toString(Merge.naiveMerge(data)));
}
}
}


The program stuck likes this: Nothing is shown after the last line "After merging:", but the program is still running until I force to terminate it.
program stuck

Answer

If you look at the arrays that came up for 3, 4, and 5, you can see that by pure coincidence all the values in all the arrays were unique. However, in your 6 case, notice that there are duplicated values (there's two 46's). Trace through your first while loop in merge. What happens if the two arrays happen to have the same value in them at some point?

Good luck!

Comments