2
\$\begingroup\$

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>();
        addAll(matrix);
    }

    private void addAll(int[][] matrix) {
        for (int[] a : matrix) {
            add(a);
        }
    }

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

        totalLength += a.length;
        heap.add(new ArrayContainer(a));
    }

    /**
     * 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;
            heap.add(arrayContainer);
        }
        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());
    }

}
\$\endgroup\$
1
\$\begingroup\$

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) {
  PriorityQueue heap = new PriorityQueue<LinkedList>(arrays.length, new Comparator<LinkedList<Integer>>() {
    public int compare(LinkedList<Integer> list1, LinkedList<Integer> list2) {
      return Integer.compare(list1.peek(), list2.peek());
    }
  });

  for(Integer[] a : arrays) { heap.add(new LinkedList<Integer>(a.asList()); }

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

  return result.toArray();
}
\$\endgroup\$
2
\$\begingroup\$

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;
        heap.add(arrayContainer);
    }

The above code would be more simple as:

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

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.....

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add);

Hmmm, maybe it still adds up to... \$O(n*m*log(n))\$

I think a better solution would be a recursive merge of the individual arrays, without the Queue.... I'll think about it some more, maybe benchmark it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.