Given k sorted integer arrays, merge them into one sorted array.

Example
Example 1:
Input: 
  [
    [1, 3, 5, 7],
    [2, 4, 6],
    [0, 8, 9, 10, 11]
  ]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Example 2:
Input:
  [
    [1,2,3],
    [1,2]
  ]
Output: [1,1,2,2,3]
Challenge
Do it in O(N log k).

Method 1 merge sort
public class Solution {
    /**
     * @param arrays: k sorted integer arrays
     * @return: a sorted array
     */
    public int[] mergekSortedArrays(int[][] arrays) {
        int len = arrays.length;
        if(len == 0) return null;
        if(len == 1) return arrays[0];
        //if(len == 2) return merge(arrays[0], arrays[1]);

        int[] leftHalf = mergekSortedArrays(Arrays.copyOfRange(arrays, 0, len/2));
        int[] rightHalf = mergekSortedArrays(Arrays.copyOfRange(arrays, len/2, len));

        return merge(leftHalf, rightHalf);
    }


    public int[] merge(int[] first, int[] second) {
        int len1 = first.length;
        int len2 = second.length;
        int[] res = new int[len1+len2];

        int i = 0;
        int j = 0;
        int index = 0;
        while(i < len1 && j < len2) {
            if(first[i] <= second[j]) {
                res[index] = first[i];
                i++;
                index++;
            } else {
                res[index] = second[j];
                j++;
                index++;
            }
        }

        while(i < len1) {
            res[index] = first[i];
                i++;
                index++;
        }

        while(j < len2) {
            res[index] = second[j];
                j++;
                index++;
        }
        return res;
    }
}


Method 2 和merge k sorted list一样思路
public class Solution {
    /**
     * @param arrays: k sorted integer arrays
     * @return: a sorted array
     */
    class Point{
        int indexX;
        int indexY;
        int value;
        public Point(int indexX, int indexY, int value) {
            this.indexX = indexX;
            this.indexY = indexY;
            this.value = value;
        }
    }
    public int[] mergekSortedArrays(int[][] arrays) {
        List<Integer> list = new ArrayList<>();
        PriorityQueue<Point> queue = new PriorityQueue<>(arrays.length, new Comparator<Point>(){
            public int compare (Point a, Point b) {
                return a.value - b.value;
            }
        });
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length > 0)
                queue.offer(new Point(i, 0, arrays[i][0]));
        }

        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            list.add(cur.value);
            if (cur.indexY < arrays[cur.indexX].length - 1) {
                queue.offer(new Point(cur.indexX, cur.indexY + 1, arrays[cur.indexX][cur.indexY + 1]));
            }
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}