# Merge two list and discarding duplicates

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
continue
if len(result) > 1 and list_2[j] == result[-1]:
j += 1
continue

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

result.append(list_1[i])
i += 1
elif list_2[j] < list_1[i]:
result.append(list_2[j])
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
continue

result.append(list_2[j])
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
continue

result.append(list_1[i])
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?

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.

• Why is merge_no_duplicates a class? Can't it be just a function? – Caridorc Oct 20 '15 at 19:27
• @Caridorc Yeah, it can. – Barry Oct 20 '15 at 19:32
• 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 – meto Oct 20 '15 at 19:47
• @meto Where do you see that in the linked doc? – Barry Oct 20 '15 at 19:51
• @meto Running a quick %%timeit test in ipython, I got lists to be about 20% faster than deques for only-right-appends. – Dougal Oct 21 '15 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))

• 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) – njzk2 Oct 21 '15 at 1:17
• 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. – pourhaus Oct 21 '15 at 3:14
• 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. – njzk2 Oct 21 '15 at 4:07
• Also even with sorted that means these results only return in sorted order, not the original order that the lists were in. – SuperBiasedMan Oct 21 '15 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.

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