Merge k Sorted Arrays

Given_k_sorted integer arrays, merge them into one sorted array.

Example

Given 3 sorted arrays:

[
  [1, 3, 5, 7],
  [2, 4, 6],
  [0, 8, 9, 10, 11]
]

return[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].

Solution: Divide conquer.

public List<Integer> mergekSortedArrays(int[][] arrays) {
    List<Integer> res = new ArrayList<Integer>();
    if(arrays.length == 0) {
        return res;
    }
    return divideConquer(arrays, 0, arrays.length - 1);
}
public List<Integer> divideConquer(int[][] arrays, int left, int right) {
    if(left == right) {
        List<Integer> l = new ArrayList<Integer>();
        for(int i = 0; i < arrays[right].length; i++) {
            l.add(arrays[left][i]);
        }
        return l;
    }
    int mid = left + (right - left) / 2;
    List<Integer> first = divideConquer(arrays, left, mid);
    List<Integer> second = divideConquer(arrays, mid + 1, right);
    return merge(first, second);
}
public List<Integer> merge(List<Integer> l1, List<Integer> l2) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    int i = 0, j = 0;
    while(i < l1.size() && j < l2.size()) {
        if(l1.get(i) < l2.get(j)) {
            res.add(l1.get(i));
            i++;
        }
        else {
            res.add(l2.get(j));
            j++;
        }
    }
    while(i < l1.size()) {
        res.add(l1.get(i));
        i++;
    }
    while(j < l2.size()) {
        res.add(l2.get(j));
        j++;
    }
    return res;
}