I am trying to implement a function that merges two ordered lists into a third (ordered) one, but duplicates have to be discarded (basically the last step of a mergesort).

I think that this code can be generalized to an arbitrary number or lists, by keeping a list of indices, rather than 2 explicit ones.

def merge_no_duplicates(list_1, list_2):
    i = j = 0
    import collections
    result = collections.deque()

    while i < len(list_1) and j < len(list_2):
        if len(result) > 1 and list_1[i] == result[-1]:
            i += 1
        if len(result) > 1 and list_2[j] == result[-1]:
            j += 1

        if list_1[i] <= list_2[j]:

            i += 1
        elif list_2[j] < list_1[i]:
            j += 1

    # we still need to consume part of list_2
    if i == len(list_1):
        while j < len(list_2):

            if list_2[j] == result[-1]:
                j += 1

            j += 1

    # still need to consume part of list_1
    if j == len(list_2):
        while i < len(list_1):

            if list_1[i] == result[-1]:
                i += 1

            i += 1
    return result

Possible improvements: factor out the repetitive parts, for example by using something similar to this helper function:

check_duplicates(my_list, index):
    if my_list[index] == result[-1]:
        index += 1

Unfortunately this won't work (index is a parameter, and will not influence the behavior of i or j). Is this possible at all?


4 Answers 4


Pick a good return type

A deque is a Double Ended QUEue. Deques are great for when you have to insert and erase from the front as well as the back. You never need this for your problem - all you ever need is to insert at the end. You just need a normal list.

Generate when you can

Rather than necessarily giving the entire result all at once, it's better to just yield the next element as you go. This is a simple change in your algorithm (just yield x instead of result.append(x)), but could have serious performance implications down the line if you have lots of large iterables. If the caller wants a full list, then can always explicitly write list(merge_no_duplicates(a, b, c)).

Use the standard when you can

There is a function that already merges sorted inputs into a single sorted output: heapq.merge. It will give you duplicates, but that seems like a much better starting point than writing everything from scratch:

def merge_no_duplicates(*iterables):
    last = object()

    for val in heapq.merge(*iterables):
        if val != last:
            last = val
            yield val

If you don't want to use heapq.merge, then you can at least use this framework to separate the "merge sorted iterables" concern from the "remove duplicates" concern.

  • \$\begingroup\$ Why is merge_no_duplicates a class? Can't it be just a function? \$\endgroup\$
    – Caridorc
    Commented Oct 20, 2015 at 19:27
  • 1
    \$\begingroup\$ @Caridorc Yeah, it can. \$\endgroup\$
    – Barry
    Commented Oct 20, 2015 at 19:32
  • \$\begingroup\$ regarding the deque: it seems that they should be faster than regular lists even if used only to append on the right: docs.python.org/3/library/collections.html#collections.deque \$\endgroup\$
    – meto
    Commented Oct 20, 2015 at 19:47
  • \$\begingroup\$ @meto Where do you see that in the linked doc? \$\endgroup\$
    – Barry
    Commented Oct 20, 2015 at 19:51
  • \$\begingroup\$ @meto Running a quick %%timeit test in ipython, I got lists to be about 20% faster than deques for only-right-appends. \$\endgroup\$
    – Danica
    Commented Oct 21, 2015 at 1:43

Code refactor suggestion

A possible better approach would be to use something along the lines of:

  • Let method accept a list of lists
  • Create iterators for each of list
  • Repeat following until no more elements:
    • Compare current element of all list
      • Push minimum to result list, iterate this list
      • Remove duplicates if any, and iterate corresponding list
  • Return the resulting list

This should do the trick rather efficiently as well as elegantly. Will possibly code it later on, but just now I'm a little busy. But just thought I would give you something to think about regarding how to improve it.

Update: No need to reinvent the wheel, so please do use (and/or accept) code example provided by Barry. Will maybe code it just for the exercise, but most likely using heapq.merge, or some union-variant, will be a better implementation.


Sometimes the code to do what you want is already there. If you think about what is like a list and supports the operation you want to perform.

Convert both lists to sets, use union(), then convert back to a list. I think the sorted() is redundant BTW:

def merge_no_duplicates(iterable_1, iterable_2):
    myset = set(iterable_1).union(set(iterable_2))
    return sorted(list(myset))

list1 = [0, 2, 6, 'dup']
list2 = [9, 1, 3, 6, 7, 'dup']

print("Sorted union as list =", merge_no_duplicates(list1, list2))
  • 1
    \$\begingroup\$ sorted is certainly not redundant, since set is not sorted. Also, because of the sort, this is O(n log(n)), while the OP's code is O(n) \$\endgroup\$
    – njzk2
    Commented Oct 21, 2015 at 1:17
  • \$\begingroup\$ The reason I think it is redundant is that I have only observed union() returning sets that are sorted. The documentation does not indicate this is guaranteed however. \$\endgroup\$
    – pourhaus
    Commented Oct 21, 2015 at 3:14
  • \$\begingroup\$ set are not sorted. what you observed is a coincidence, linked to the fact that small integers tend to be inserted in ordered buckets. Example, on my machine right now set([1,2,3]) (appears to be ordered) but set([1, 1000]) prints {1000, 1}. Result may differ from an environment to the other. \$\endgroup\$
    – njzk2
    Commented Oct 21, 2015 at 4:07
  • \$\begingroup\$ Also even with sorted that means these results only return in sorted order, not the original order that the lists were in. \$\endgroup\$ Commented Oct 21, 2015 at 15:22

Hmmm, objects in an ordered list.... Are we overthinking?

def combine_remove_and_sort(list1, list2):
    return sorted(list(set(list1+list2)))

Kinda lazy but saves time for the really complex problems.

  • \$\begingroup\$ "Saves time"? In what sense, lazyness when writing? Not in performance time if we're talking about lists of a non trivial small size. \$\endgroup\$
    – holroy
    Commented Oct 22, 2015 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.