Merge N sorted arrays

Problem

Given n sorted arrays. Merge them into a single sorted array.

Solution

While merging two sorted sequences we always look at the front element and pick the lowest of them. Then the next element from the picked array takes place of the previous element and the process continues till one of them is empty. In case of N arrays if we do the same process, the time complexity of checking the front elements is O(n). If there are N arrays all having elements of the order of N. Then there are O(N^2) elements and for every element we will have to find the minimum in O(n) time. So the overall complexity will be O(N^3). We can decrease the complexity to O(N^2 log N) by adding the arrays to a heap. Each node of the heap will be an array whose priority will be decided by the front element. So if we pick the root of the heap we will find the smallest of the front elements of all the arrays. After adding it to the resultant array we will remove it and again insert the array into the heap, This process will take O(log N). So the overall complexity will become O(N^2 log N)

For implementing this, we created a class ArrayContainer which will hold the array inside an object. And whose natural ordering will be decided by the front element of the array. So when all the array containers are  inserted into the heap, top element will be the array with smallest front element.

Code

/*
For problem and solution description please visit the link below
http://www.dsalgo.com/2013/02/merge-n-sorted-arrays.html
*/
package com.dsalgo;
import java.util.PriorityQueue;


public class MergeNSortedArrays
{
 public static void main(String[] args)
 {
  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};
  int[]result=mergeNArrays(new int[][]{arr1,arr2,arr3,arr4});
  for(int i:result)
  {
   System.out.print(i+",");
  }
 }

 private static int[] mergeNArrays(int[][] sortedArrays)
 {
  int totalLength=0;
  PriorityQueue < ArrayContainer > heap=new PriorityQueue < ArrayContainer >();
  
  for(int i=0;i < sortedArrays.length;++i)
  {
   totalLength+=sortedArrays[i].length;
   heap.add(new ArrayContainer(sortedArrays[i]));
  }
  int[]result=new int[totalLength];
  int index=0;
  while(!heap.isEmpty())
  {
   ArrayContainer arrayContainer=heap.poll();
   result[index++]=arrayContainer.getNextInt();
   if (arrayContainer.isEmpty())
    continue;
   heap.add(arrayContainer);
  }
  return result;
 }
 private static class ArrayContainer implements Comparable < ArrayContainer >
 {
  private int startIndex;
  private int[]array;
  public ArrayContainer(int[]array)
  {
   this.array=array;
   startIndex=0;
  }
  public boolean isEmpty()
  {
   return startIndex==array.length;
  }
  public int peek()
  {
   return array[startIndex];
  }
  public int getNextInt()
  {
   return array[startIndex++];
  }
  @Override
  public int compareTo(ArrayContainer o)
  {
   return new Integer(peek()).compareTo(o.peek());
  }
  
 }
}