CODEWITHSUNDEEP
pythonmerge
phil12
phil12

Reputation: 135

Merging three lists together

For fun, I am trying to implement k way merge sort where k =3. I do not have trouble with calling mergesort recursively but I am trying to merge three lists together but I am not getting a sorted list. The basic idea is that I compare the first element of every list and if it is the smallest I append it to a list. I repeat the process for all the arrays.

def three_merge(a,b,c):
    i =0
    j =0
    k=0
    list = []
    while(i < len(a) or j < len(b) or k < len(c)):
        while(a[i] <= b[j] and a[i] <= c[k]):
            list.append(a[i])
            i=i+1
            print i
        while(b[j] <= a[i] and b[j] <= c[k]):
            list.append(b[j])
            j=j+1
            print j
        while(c[k] <= a[i] and c[k] <= b[j]):
            list.append(c[k])
            k=k+1
            print k
   return list    

a = [1,2]
b = [-5,10]
c = [-11, 100]
print three_merge(a,b,c)

Upvotes: 0

Views: 1294

Answers (3)

georg
georg

Reputation: 214949

Here's a simple function for n-way merge. Feel free to ask if you have questions:

def merge(*args):
    lst = list(args)
    idx = [0] * len(lst)
    out = []

    while lst:
        m = 0
        for i in range(len(lst)):
            if lst[i][idx[i]] < lst[m][idx[m]]:
                m = i
        out.append(lst[m][idx[m]])
        idx[m] += 1
        if idx[m] >= len(lst[m]):
            del lst[m]
            del idx[m]

    return out


print merge([1,2,11], [2,9], [8]) # [1, 2, 2, 8, 9, 11]

Upvotes: 1

Michael J. Barber
Michael J. Barber

Reputation: 25032

The problem is that you advance the indices i, j, k for each value you append to the sorted list, which means that the index is one greater than the length of the corresponding input list after taking all elements from the list. So when you compare the values of the elements for the different input lists, you eventually hit a point where you are trying to do, in effect, a[len(a)], while will always give an index error.

Upvotes: 1

Andrea Sindico
Andrea Sindico

Reputation: 7440

why don't you consider a merge of three lists as a composition of two merges of two lists 

def merge(a,b):
    L = a
    l = b
    i = 0
    j = 0
    res = []
    if (len(b)>len(a)):
        L=b
        l=a
    #print L
    #print l
    while (i<len(L)):
        if(len(l)>0):
            while (j<len(l)):
                if (L[i]<=l[j]):
                    res.append(L[i])
                    del L[i]
                    break
                else:
                    res.append(l[j])
                    del l[j]
        else:
            #print res
            res = list(res+L)
            L=[]
            break
    if len(l)>0:
        res = list(res+l)
        l=[]
    return res

def threeMerge(a,b,c):
    return merge(merge(a,b),c)

aa = [1,2]
bb = [-5,3,20]
cc= [-11, 23,45]
print threeMerge(aa,bb,cc)

Upvotes: 0

Related Questions