CODEWITHSUNDEEP
pythonarrayslistsortingmerge
MrSoLoDoLo
MrSoLoDoLo

Reputation: 375

How to merge k number of sorted lists?

def merge(list1, list2):
    results = []
    while list1 and list2:
        if list1[0] < list2[0]:
            results.append(list1.pop(0))
        else:
            results.append(list2.pop(0))
    results.extend(list1)
    results.extend(list2)
    return results

Here is the standard algorithm to merge 2 sorted lists into 1. However, how can we merge multiple sorted lists into 1? 

l = [[8, 10, 12], [4, 5, 9], [2, 11]]  
merge(l)  
>>> [2, 4, 5, 8, 9, 10, 11, 12]

Upvotes: 0

Views: 2326

Answers (6)

Tim Diels
Tim Diels

Reputation: 3416

An easy and efficient way is heapq.merge:

>>> lists = [[8, 10, 12], [4, 5, 9], [2, 11]]
>>> list(heapq.merge(*lists))
[2, 4, 5, 8, 9, 10, 11, 12]

Glancing at CPython's implementation, it looks similar to the direct k-way merge answer, so I would guess that heapq.merge is O(n log(k)) as well, though the docstring does not guarantee this.

Upvotes: 1

Lenny Gonzalez
Lenny Gonzalez

Reputation: 153

from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = point = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))
        while not q.empty():
            val, node = q.get()
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

Using a Priority Queue optimizes the comparison process

  1. Time Complexity: O(n log(k)) where k is the number of linked lists:

    • The comparison cost will be reduced to O(log k) for every pop and insertion to priority queue. But finding the node with the smallest value just costs O(1) time.

  2. Space Complexity:

    • O(n) Creating a new linked list costs O(n) space
    • O(k) The code above present applies in-place method which cost O(1) space.
    • And the priority queue(often implemented with heaps) costs O(k) space (it's far less than N in most situations)

Upvotes: 0

vash_the_stampede
vash_the_stampede

Reputation: 4606

Flatten with list comprehension and then sort 

print(sorted([j for i in l for j in i]))
# [2, 4, 5, 8, 9, 10, 11, 12]

Upvotes: 0

slider
slider

Reputation: 12990

You can use your own merge with reduce:

from functools import reduce

l = [[8, 10, 12], [4, 5, 9], [2, 11]]

merged = reduce(merge, l)
print(merged)
# [2, 4, 5, 8, 9, 10, 11, 12]

This has running time O(kn). You could merge (unique) pairs until you have 1 final list left, which would improve it to O(n log k) (as the number of lists to merge reduces by half every time).

Upvotes: 2

Dani Mesejo
Dani Mesejo

Reputation: 61910

You could implement direct k-way merge using a heap and queues:

import heapq
from collections import deque


def k_merge(*lists):
    queues = [queue for queue in map(deque, lists)]

    heap = []
    for i, lst in enumerate(queues):
        heap.append((lst.popleft(), i))

    heapq.heapify(heap)

    result = []
    while heap:
        value, index = heapq.heappop(heap)
        result.append(value)

        if queues[index]:
            heapq.heappush(heap, (queues[index].popleft(), index))

    return result


print(k_merge(*[[8, 10, 12], [4, 5, 9], [2, 11]]))

Output

[2, 4, 5, 8, 9, 10, 11, 12]

If you have k lists and n elements this approach is O(nlogk)

Upvotes: 4

Christian Sloper
Christian Sloper

Reputation: 7510

You can just sort it using sorted():

from itertools import chain

l = [[8, 10, 12], [4, 5, 9], [2, 11]]

sorted(chain(*l))

Gives result:

[2, 4, 5, 8, 9, 10, 11, 12]

Upvotes: 2

Related Questions