# Simple Java Merge Sort

• For this problem, use merge sort is simple and fast, I wonder why some guys solve it use PriorityQueue.

I think the complexity is k * n * logk. Because the recursion depth is logK, and in each level, every element will be compared.

``````public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
return mergeKLists(lists, 0, lists.length - 1);
}
private ListNode mergeKLists(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
} else if (start < end){
int mid = (end - start) / 2 + start;
ListNode left = mergeKLists(lists, start, mid);
ListNode right = mergeKLists(lists, mid + 1, end);
return mergeTwoLists(left, right);
} else {
return null;
}
}
``````

mergeTwoLists is base on the Merge Two Sorted Lists problem.

• The reason people use priority queue is that it reduces the time to O(nlogk). I think it's better than O(nk*logk).

• Very Nice Solution. Thanks.

• @janecuan @robinjia No, I believe they have the same time complexity. If n denotes the total number of nodes (for [[1,2,3], [4], [5,6]], k = 3, n = 6), both algorithms have complexity O(nlogk).
For PriorityQueue, every node is polled from a pq of size k, so time complexity is n * logk.
For divide and conquer, recursion depth is logk. In each level, you need merge n nodes. The time complexity for each level is O(n) rather than O(k*n) (e.g. if you have 4 lists with 10, 20, 30, 40 nodes, merge list 1 and list 2 you need 30x operations while merge list 3 and 4 you need 70x operations, and 100x in total. )

If n denotes the number of nodes in each list, then both algorithms have complexity O(nklogk)

• @aruo so O(nlogk) or O(nklogk)?? should be O(nlogk)

• @aruo @robinjia Nice solution and nice explanation of the runtime complexity. I agree with both of you! Really effective divide and conquer way of solving this without the need of priority queue. Thanks!

• I think this is a little more readable:

``````public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return sort(lists, 0, lists.length - 1);
}

private ListNode sort(ListNode[] lists, int lo, int hi) {
if (lo >= hi) return lists[lo];
int mid = lo + (hi - lo) / 2;
ListNode l1 = sort(lists, lo, mid);
ListNode l2 = sort(lists, mid + 1, hi);
return merge(l1, l2);
}

private ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
}
l2.next = merge(l1, l2.next);
return l2;
}
}
``````

• @robinjia Its a linked list not an array

• @selim This is an array of linked list nodes, lol its supposed to be an actual linked list

• @aruo @janecuan The complexity of Merge Sort and PriorityQueue are the some, both have O(nklogk)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.