# Merge k sorted lists in Java

I hava a question similiar with mege in Python but I am trying to write Java code. Here is my code: The input is: The first line - a number of arrays (k); Each next line - the first number is the array size, next numbers are elements.

Max k is 1024. Max array size is 10*k. All numbers between 0 and 100. Memory limit - 10MB, time limit - 1s. Recommended complexity is k ⋅ log(k) ⋅ n, where n is an array length.

Example input:

4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84


Example output:

1 2 4 8 16 20 26 42 58 61 64 65 69 84 86 88 96 96


I get memory limit errors. I use System.gc() to clear the memory but I recieve timeout error

Here is my code:

import java.io.BufferedReader;
import java.io.IOException;
public static void main(String[] args) throws IOException {

short[][] arrays = new short[k][];

int arrayLength = 0;
int[] minPositionInArrays = new int[k];
for (int i = 0; i < k; i++) {
String[] elements = str.split(" ");
arrays[i] = new short[Short.valueOf(elements[0]) + 1];
for (int j = 0; j < elements.length; j++) {
arrays[i][j] = Short.valueOf(elements[j]);
}
arrayLength += Short.valueOf(elements[0]);
minPositionInArrays[i] = 1;

if (arrayLength % 100 == 0) {
System.gc();
}
}

StringBuilder sb = new StringBuilder();
int currentArrayNumber = 0;
int currentPositionInArray = minPositionInArrays[currentArrayNumber];
while (arrayLength > 0) {
short currentMinValue = 101;
for (int i = 0; i < k; i++) {
if (minPositionInArrays[i] <= arrays[i][0] && currentMinValue >= arrays[i][minPositionInArrays[i]]) {
currentMinValue = arrays[i][minPositionInArrays[i]];
currentArrayNumber = i;
currentPositionInArray = minPositionInArrays[i] + 1;
}
}
sb.append(currentMinValue + " ");
minPositionInArrays[currentArrayNumber] = currentPositionInArray;
arrayLength--;
}

System.out.println(sb.toString().trim());
}
}

• Why is there 1x a 1, but 2x a 96 in the output? – RobAu Sep 10 '19 at 11:38
• @RobAu Because the first number on each line isn't part of the numbers to be merged, it is telling how many numbers are on that line (or in that array) – Imus Sep 17 '19 at 8:13
• Ah I misread. Thanks! – RobAu Sep 17 '19 at 10:32

Are you getting the correct output with the recommended complexity? It's been a long time since I've written my own sort but start by confirming that before any of my recommendations below.

I suspect str.split(" ") is causing problems for you because you're creating lots of strings which you're about to parse and then throw away. How about parsing the integers directly from str in a single pass instead?

Try changing sb.append(currentMinValue + " ") to sb.append(currentMinValue).append(" "). It might be a small optimization but it's easy to do.

How about splitting your main into two methods? The first for everything that uses reader, the second for everything that uses sb. Besides improving the structure of the program this provides a natural point for garbage collection.

What command-line args are you giving to the JVM? Since you know your memory limit try allocating it all at the start to save time allocating more memory later. You might also play with different garbage collection strategies. As you're discovering, forcing garbage collection isn't a good idea. If you're correctly setting the maximum in the JVM it should automatically garbage collect as needed to prevent running out of memory.

Hope at least one of these suggestions helps. I'm curious what gives the biggest improvement.

I was curious about why you kept the initial size inside each of the arrays until I finaly noticed the
arrays[i][0] in the check if that array still has elements to proces during the algorithm. If we replace that with arrays[i].length-1 we no longer need to store those.

Another major issue, like Nathan pointed out is how many String objects you're creating while parsing the input. The easiest solution to this is to use a Scanner instead of a BufferedReader. That way, you can directly read the nextShort().

    Scanner reader = new Scanner(new InputStreamReader(System.in));

short[][] arrays = new short[k][];

int arrayLength = 0;
int[] minPositionInArrays = new int[k]; // note here: now correctly initialised to 0's
for (int i = 0; i < k; i++) {
arrays[i] = new short[size];
for (int j = 0; j < size; j++) {
}
arrayLength += size;
}