Merge k Sorted Arrays

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 1: Divide and Conquer or Binary Merge O(nlogk); O(logk)

    public List<Integer> mergekSortedArrays(int[][] arrays) {
        List<Integer> res = new ArrayList<>();
        int[] newArray = divide(arrays, 0, arrays.length - 1);
        for (int i = 0; i < newArray.length; i++) {
            res.add(newArray[i]);
        }
        return res;
    }

    private int[] divide(int[][] arrays, int s, int e) { //O(logk)
        if (s == e) {
            return arrays[s];
        }
        return merge(divide(arrays, s, s + (e - s) / 2),
                divide(arrays, s + (e - s) / 2 + 1, e));
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] newArray = new int[m + n];
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < m && j < n) {
            newArray[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < m) {
            newArray[k++] = nums1[i++];
        }
        while (j < n) {
            newArray[k++] = nums2[j++];
        }
        return newArray;
    }

Solution 2: Heap

class Element {
    public int row, col, val;
    Element(int row, int col, int val) {
        this.row = row;
        this.col = col;
        this.val = val;
    }
}

public class Solution {
    private Comparator<Element> ElementComparator = new Comparator<Element>() {
        public int compare(Element left, Element right) {
            return left.val - right.val;
        }
    };

    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    public int[] mergekSortedArrays(int[][] arrays) {
        if (arrays == null) {
            return new int[0];
        }

        int total_size = 0;
        Queue<Element> Q = new PriorityQueue<Element>(
            arrays.length, ElementComparator);

        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0) {
                Element elem = new Element(i, 0, arrays[i][0]);
                Q.add(elem);
                total_size += arrays[i].length;
            }
        }

        int[] result = new int[total_size];
        int index = 0;
        while (!Q.isEmpty()) {
            Element elem = Q.poll();
            result[index++] = elem.val;
            if (elem.col + 1 < arrays[elem.row].length) {
                elem.col += 1;
                elem.val = arrays[elem.row][elem.col];
                Q.add(elem);
            }
        }

        return result;
    }