CODEWITHSUNDEEP
pythonarraysalgorithmsortinglanguage-agnostic
Rudziankoŭ
Rudziankoŭ

Reputation: 11251

Merge sorted arrays algorithm

I have to create algorithm for merging sorted arrays. Here is what I did:

import sys

lists = [[1,2,3], 
         [-100, 70], 
         [23, 50]]
pivot = [0] * len(lists) # [0, 0, 0]
finalSorted = []


for _ in range(sum(len(x) for x in lists)): # quantity of items in 2D array 
    smallest = sys.maxint
    index_of_smallest = -1      
    for indx, list in enumerate(lists):
        if pivot[indx] < len(list):
            current = list[pivot[indx]]
            if current <= smallest:
                smallest = current
                index_of_smallest = indx

    finalSorted.append(smallest)
    pivot[index_of_smallest] = pivot[index_of_smallest]+1

print(finalSorted) #[-100, 1, 2, 3, 23, 50, 70]

Questions:

  1. Is this the best way of doing this?
  2. Is algorithmic complexity kn^2? Where 'k' is average array length and n is quantity of arrays.
  3. Is it good only for cases where k is much bigger then n? Where is the point of such k and n having which quicksort here become better solution?

Upvotes: 1

Views: 1710

Answers (4)

Paul Panzer
Paul Panzer

Reputation: 53029

Python's own standard lib provides a heap based solution heapq.merge which I would assume to be O(kn log n). I doubt you can do better than O(kn log n).

The source of heapq.merge is not too long, if you want to have a look.

Upvotes: 0

程名锐
程名锐

Reputation: 39

There is a quite similar question on leetcode: https://leetcode.com/problems/merge-k-sorted-lists/description/ which merge k sorted lists and the time complexity is O(Nlogk) where N is the total number of the k lists.

The algorithm's main method is to build a min heap of size k, and add elements to it. Since there was a detailed explanation on the leetcode website and I suggested you may take a look at it.

Upvotes: 0

C. Feenstra
C. Feenstra

Reputation: 593

this is somewhat faster -- about 1.5x from my experimentation:

from itertools import izip_longest

final = []
second = lambda x: x[1]
while any(lists):
    idx, _ = min(enumerate(next(izip_longest(*lists, fillvalue=sys.maxint))), key=second)
    final.append(lists[idx].pop(0))

EDIT: I guess if you're thinking about this in more of a theoretical sense (i.e. as an interview question) this isn't the best answer--a good example of using & abusing built-in python functions though :P

Upvotes: 0

user1767754
user1767754

Reputation: 25094

That's a popular programming interview question. The most elegant solution i saw so far was the following:

from Queue import PriorityQueue

def mergeKLists(lists):
    dummy = ListNode(None)
    curr = dummy
    q = PriorityQueue()
    for node in lists:
        if node: q.put((node.val,node))
    while q.qsize()>0:
        curr.next = q.get()[1]
        curr=curr.next
        if curr.next: q.put((curr.next.val, curr.next))
    return dummy.next

All Credit to> https://discuss.leetcode.com/topic/33609/10-line-python-solution-with-priority-queue

Upvotes: 1

Related Questions