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;
import java.io.InputStreamReader;
public class TaskFSolution {   
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int k = Integer.valueOf(reader.readLine());

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

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

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

        reader.close();

        StringBuilder sb = new StringBuilder();
        int currentArrayNumber = 0;
        int currentPositionInArray = minPositionInArrays[currentArrayNumber];
        while (arrayLength &gt; 0) {
            short currentMinValue = 101;
            for (int i = 0; i &lt; k; i++) {
                if (minPositionInArrays[i] &lt;= arrays[i][0] &amp;&amp; currentMinValue &gt;= 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());
    }
}
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.