Find Kth Largest Integer from List of Sorted Integers List

Hello everybody!

No I haven't died, just been a buzzy buzzy bee. Buzzzzzzzzzzzzzz.

Anywho, before I become senile from old age I decided to get some programming practice and decided to take on the challenge of:

Given an array of arrays of sorted ints. Returned the kth largest. 

To give credit where credit is due, I found this in a list of questions that a Cal student composed.

How do we find the kth largest from multiple lists?

How about merging all lists into one list? Then we can easily find the Kth largest element.

The fact that the sublists are already sorted will help a lot, since merging two sorted arrays is doable in linear time.

So here's the algorithm, perform a merge sort on the list of lists.

When merging, combine the two lists into a single list.

With the merged list, find the kth largest by subtracting k from the list size.

 int findKthLargest(int k, ArrayList<ArrayList<Integer>> list)
 {
  ArrayList<Integer> merged = this.mergeSort(list);
  return merged.get(merged.size()-k);
 }
 
 private ArrayList<Integer> mergeSort(ArrayList<ArrayList<Integer>> list)
 {
  
  // Base Case: when list size only has one list, return it
  if (list.size() == 1) {
   return list.get(0);
  }

  // Recursive case: when the list size > 1 continually break down the list
  // merge the lists and return it
  int middle = list.size() / 2;
  
  // Divide and conquer
  ArrayList<ArrayList<Integer>> lowList = new ArrayList<ArrayList<Integer>>(list.subList(0, middle));
  ArrayList<ArrayList<Integer>> highList = new ArrayList<ArrayList<Integer>>(list.subList(middle, list.size()));

  ArrayList<Integer> mergedLowList = mergeSort(lowList);
  ArrayList<Integer> mergedHighList = mergeSort(highList);

  // Starting from the base case, merge the lists together
  return merge(mergedLowList, mergedHighList);
 }
 
 private ArrayList<Integer> merge(ArrayList<Integer> list1, ArrayList<Integer> list2)
 {
  ArrayList<Integer> merged = new ArrayList<Integer>();
  
  int j = 0;
  int i = 0; 
  
  while(i < list1.size())
  {
   // We added all of list 2 so just add list 1
   if(j == list2.size())
   {
    merged.add(list1.get(i));
    i++;
   }
   // Add the lower one
   else if(list1.get(i) <= list2.get(j))
   {
    merged.add(list1.get(i));
    i++;
   }
   else
   {
    merged.add(list2.get(j));
    j++;
   }
  }
  
  // We added all of list 1 so just add list 2
  while(j < list2.size())
  {
   merged.add(list2.get(j));
   j++;
  }
  
  return merged;
 }

Code on Github