Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Merge a Number of Sorted Arrays

Explore an efficient approach to merging multiple sorted arrays using divide and conquer techniques in Java. Understand the algorithm’s recursive structure and how it improves over naive sorting methods to achieve better time complexity, a vital skill for coding interviews.

We'll cover the following...

Solution#1

Java
class Merge {

 public static int n = 4;



 public static ArrayList < Integer > mergeSortedArrays(int[][] arr, ArrayList < Integer > Output) {

  //traversing the 2-D array and appending all arrays into an ArrayList

  for (int i = 0; i < arr.length; i++) {

   for (int j = 0; j < arr[i].length; j++) {

    //adding into the ArrayList

    Output.add(arr[i][j]);

   }

  }

  //sorting the ArryList using the inbuilt sort function

  Collections.sort(Output);

  return Output;

 }



 public static void main(String args[]) {

  // 2D input array 

  int[][] arr = {{16, 25, 36}, {2, 9, 15}, {22, 55, 67}, {79, 38, 99}}; 

  ArrayList < Integer > Output = new ArrayList < Integer > ();



  System.out.print(mergeSortedArrays(arr, Output));



 }

}

A naive solution to this problem would be:

  1. Append all the arrays one after another in an ArrayList say Output.
  2. Next, simply sort the Output using the built-in Java function, i.e., Collections.sort();.

Time complexity

Appending kk sorted arrays into an ArrayList array would take O(n∗k)O(n*k) time. Since Collections.sort() runs in O(size∗log(size))O(size*log(size)) and the size of Output is (n∗k)(n*k) ...