Simple Java Merge Sort


  • 22

    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.


  • 0
    J

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


  • 0
    N

    Very Nice Solution. Thanks.


  • 12
    A

    @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)


  • 0
    A

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


  • 0
    T

    @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!


  • 3
    S

    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;
        }
    }
    

  • 0
    B

    @robinjia Its a linked list not an array


  • 0
    B

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


  • 0

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


Log in to reply
 

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