Matt - 6 months ago 35

Java Question

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

Steps:

- merge the first and second arrays
- merge the above resulting array with the 3rd array
- merge the above resulting array with the 4th array
- ... 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.

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!