Python: Combining two sorted lists (and keeping them sorted) without using built-in sort

Question

I found this merge sort solutions online and I'm wondering if while loops is the way to go or if there is also a way of using 2 for loops and comparing those.

def merge(l, m):
    result = []
    i = j = 0
    total = len(l) + len(m)
    while len(result) != total:
        if len(l) == i:
            result += m[j:]
            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(m[j])
            j += 1
    print result

merge([1,2,6,7], [1,3,5,9])

ShadowRanger · Accepted Answer · 2015-10-04 23:56:24Z

2

Python's builtin sorted would actually be pretty efficient at this (since the TimSort it uses takes advantage of existing ordering in subsets of a list). That said, there is a built-in that avoids the need to even construct a new list like sorted (or your solution) would: heapq.merge

It's designed precisely for scenarios where you have existing lists that are each independently sorted. It's a generator function, so it doesn't require the creation of a new list at all. If you are trying to do this to learn, enjoy yourself, but if this is for "real" code, use the included batteries and avoid reinventing the wheel.

answered Oct 4, 2015 at 23:56

ShadowRanger

158k12 gold badges221 silver badges316 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

LetzerWille · Accepted Answer · 2015-10-04 23:59:49Z

1

You can easily change while to for:

def merge_for(l,m):
    result = []
    i = j = 0
    total = len(l) + len(m)

    for k in range(total):

        if len(l) == i:
            result += m[j:]
            print("append el {} at index {}".format(m[j], k))

            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            print("append el {} at index {}".format(l[i], k))
            i += 1
        else:
            result.append(m[j])
            print("append el {} at index {}".format(m[j], k))
            j += 1

    print(result)


print(merge_for([1,2,6,7], [1,3,5,9]))

append el 1 at index 0
append el 1 at index 1
append el 2 at index 2
append el 3 at index 3
append el 5 at index 4
append el 6 at index 5
append el 7 at index 6
append el 9 at index 7

[1, 1, 2, 3, 5, 6, 7, 9]

edited Oct 4, 2015 at 23:59

answered Oct 4, 2015 at 23:23

LetzerWille

5,6965 gold badges26 silver badges28 bronze badges

2 Comments

Intrepid Diamond Over a year ago

Ah, gotchya. So pretty much k is unused, and you create your own "mock" for loops (i += 1 & j += 1)?

LetzerWille Over a year ago

@IntrepidDiamond put k to work, now it prints the index of insersion

naimetti · Accepted Answer · 2015-10-05 00:13:19Z

0

A solution using using a generator:

from itertools import chain
def merge(l1,l2):
    i,j = 0,0
    try:
        while True:
            if l1[i] < l2[j]:
                yield l1[i]
                i +=1
            else:
                yield l2[j]
                j+=1
    except IndexError:
        for e in chain(l1[i:],l2[j:]):
            yield e

[x for x in merge([1,2,6,7], [1,3,5,9])]

[1, 1, 2, 3, 5, 6, 7, 9]

answered Oct 5, 2015 at 0:13

naimetti

1757 bronze badges

1 Comment

naimetti Over a year ago

The heapq.merge answer is the right. This is just for fun and learning.

Padraic Cunningham · Accepted Answer · 2015-10-05 00:36:24Z

0

If you have a sorted list you bisect.insort the other:

from bisect import insort

a,b = [1,2,6,7], [1,3,5,9]

for ele in b:
    insort(a, ele)
print(a)
[1, 1, 2, 3, 5, 6, 7, 9]

answered Oct 5, 2015 at 0:36

Padraic Cunningham

181k30 gold badges264 silver badges327 bronze badges

Collectives™ on Stack Overflow

Python: Combining two sorted lists (and keeping them sorted) without using built-in sort

4 Answers 4

Comments

2 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related