# Merge N sorted list

Given n sorted lists, merge them.

This is a fairly common question, attributed to plenty of interview question websites.

I'm looking for code-review, optimizations and best practices. I'm also verifying complexity to be $O(n*m*log(n))$, where n is the number of list and m is the size of longest list.

public final class MergeNSortedArray {

private final PriorityQueue<ArrayContainer> heap;
private int totalLength;

public MergeNSortedArray() {
heap = new PriorityQueue<MergeNSortedArray.ArrayContainer>();
}

/**
* All rows of the matrix are expected to be sorted.
* Else results are unpredictable.
*
* @param matrix
*/
public MergeNSortedArray(int[][] matrix) {
if (matrix == null) {
throw new NullPointerException("The input matrix is null");
}
heap = new PriorityQueue<MergeNSortedArray.ArrayContainer>();
}

for (int[] a : matrix) {
}
}

/**
* The input array is expected to be sorted, else results are unpredictable.
* @param a
*/
if (a.length == 0) { throw new IllegalArgumentException("Array size should be greater then zero."); }

totalLength += a.length;
}

/**
* Keeps a counter, to keep track of current element to be considered to
* sort.
*
* Any element before the currentIndex, has already been placed in the sorted array.
*
*/
private static class ArrayContainer implements Comparable<ArrayContainer> {
private int index;
private int[] array;

public ArrayContainer(int[] array) {
this.array = array;
}

public boolean isFull() {
return index == array.length;
}

public int peek() {
return array[index];
}

public int getIntAndIncrement() {
return array[index++];
}

@Override
public int compareTo(ArrayContainer o) {
return new Integer(peek()).compareTo(o.peek());
}
}

public int[] mergeNArrays() {
int[] result = new int[totalLength];
int index = 0;

while (!heap.isEmpty()) {
final ArrayContainer arrayContainer = heap.poll();
result[index++] = arrayContainer.getIntAndIncrement();
if (arrayContainer.isFull())
continue;
}
return result;
}
}

public class MergeNSortedArrayTest {

@Test
public void testMerge() {
int[] arr1 = {2,4,6,8,9,12,14,16};
int[] arr2 = {3,6,7,9,22,25,28};
int[] arr3 = {2,5,7,8,10,11,16};
int[] arr4 = {4,8,23,26,28};

MergeNSortedArray msa = new MergeNSortedArray(new int[][]{arr1, arr2, arr3, arr4});

int[] expected = {2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9, 9, 10, 11, 12, 14, 16, 16, 22, 23, 25, 26, 28, 28};

assertArrayEquals(expected, msa.mergeNArrays());
}

}


I shrank your code a lot. Spacing and brackets can be fixed, not too familiar with java convention.

public static Integer[] mergeArrays(Integer[][] arrays, int totalLength) {
return Integer.compare(list1.peek(), list2.peek());
}
});

ArrayList<Integer> result = new ArrayList<Integer>();
while (heap.size() > 0) {
if (current.peekFirst() != null) { heap.add(current); }
}

return result.toArray();
}


Your code deliberately fails on an empty input array. This is an artificial constraint. The code would actually work (or should actually work) except you have the condition that throws an exception:

  if (a.length == 0) { throw new IllegalArgumentException("Array size should be greater then zero."); }


You have also put that whole thing on a single line (with braces which is not totally bad). Get rid of that condition, it makes no sense. Why is it a problem to merge an empty array?

You have the following compare method:

    @Override
public int compareTo(ArrayContainer o) {
return new Integer(peek()).compareTo(o.peek());
}


This creates an Integer object, when the better (faster) approach would be:

    @Override
public int compareTo(ArrayContainer o) {
return Integer.compare(peek(), o.peek());
}


The Integer.compare static method will not need to create the Integer objects from the ints.

I like the continue and break statements in Java, and use them regularly, but, your use of continue here is not necessary (and you do not use a 'braced' 1-liner here....!!!):

    while (!heap.isEmpty()) {
final ArrayContainer arrayContainer = heap.poll();
result[index++] = arrayContainer.getIntAndIncrement();
if (arrayContainer.isFull())
continue;
}


The above code would be more simple as:

    while (!heap.isEmpty()) {
final ArrayContainer arrayContainer = heap.poll();
result[index++] = arrayContainer.getIntAndIncrement();
if (!arrayContainer.isFull()) {

Finally, for reasons I can't quite rationalize, I don't like the algorithm. I think your analysis of the complexity ( $O(n*m*log(n))$ ) is optimistic, I think it is slower than that. The issue is that... you loop through all the data totalLength times (which is essentially n * m): Each time you do that, you do a poll, and an add to the heap. each of these are log(n) operations.....
Hmmm, maybe it still adds up to... $O(n*m*log(n))$