# Takes in two sorted lists and outputs a sorted list that is their union

Write a function that takes in two sorted lists and outputs a sorted list that is their union

Could anyone help me to improve this code and make it more user-friendly? We are not supposed to use any built-in Python functions, but rather develop our own efficient algorithms.

def answer(list1, list2):

len1 = len(list1)
len2 = len(list2)

final_list = []
j = 0
k = 0

for i in range(len1+len2):

if k == len1:
final_list.append(list2[j])
j += 1
continue

if j == len2:
final_list.append(list1[k])
k += 1
continue

if list1[k] < list2[j]:
final_list.append(list1[k])
k += 1

else:
final_list.append(list2[j])
j += 1

return final_list

print answer([1, 2 , 17, 18, 100], [3, 3, 4, 5, 15, 19, 20, 101])

• Could you please join the 2nd Monitor and talk about your requirements? – Caridorc Sep 8 '15 at 18:20
• @Caridorc You might want to include a link to it: The 2nd Monitor, Code Review General Chatroom – Simon Forsberg Sep 8 '15 at 18:29
• "We are not supposed to use any built-in Python functions" you may want to clarify that and say exactly what functions are prohibited. – Simon Forsberg Sep 8 '15 at 18:30

You could pick better names for your variables. Definitely answer should be something else, like sorted_union. result would be better than final_list. And list1 and len1 aren't great, though you have limited options there.

You should also add a docstring. They're basically string literals that appear at the start of a class or function. They're programmatically accessible comments that will allow you to see what the function does, and you already have one in your brief, so just add the syntax to include it:

def answer(list1, list2):
"""Takes two sorted lists and returns their union as a sorted list."""


Also since you call for i in range but don't need i, a commonly accepted Python style is to actually use _ instead of i. Using an underscore signals that you don't need the value, it's just there to fit the for loop syntax.

You actually could shortcircuit the loop when j or k have reached the end. You know you'll no longer need anything but the rest of list2 in this case:

    if k == len1:
final_list.append(list2[j])
j += 1
continue


So why not just use extend to add the rest of list2 on to final_list and break the loop?

    if k == len1:
final_list.extend(list2[j:])
break


I think your solution is ok.

Instead of using continue, consider using if..elif..elif..else:

if k >= len1:
...
elif j >= len2:
...
elif ...:
...
else:
...


Also, the test k >= len1 is an example of "defensive programming". It protects against k skipping over len1 when being incremented in the loop. Also, the expression list1[k] doesn't make sense unless k < len1, and the negation of that is k >= len1 which is another good reason to use it in the if statement.

If you've learned about xrange() then I would use that instead of range() -- see these SO answers:

https://stackoverflow.com/questions/135041/should-you-always-favor-xrange-over-range

Otherwise it looks good!

Efficiency

• If you can use the append method I would assume you are also allowed to use the extend method. In that case, I'd rewrite your first two control statements, checking if you've gotten to the end of one of the original lists, like so (also making the control statements more readable/succinct/performant with an elif:

if k == len1:
final_list.extend(list2[j:])
break
elif j == len2:
final_list.extend(list1[k:])
break


I may have missed something in the logic, but I think this should get to what you want and spare you a lot of unneeded iterations once you have exhausted one of the original lists.

• Use iterators instead of lists when possible. Here that would be using xrange instead of range in your for loop. Not super important, but it's good practice.

• You could definitely use better variable names, and I think @Jaime's use of idx1 and idx2 is a good example of this. Since you have list1 doesn't it make more sense to have idx1 rather than a reader having to guess whether j or k applies to list1? Similarly, a better name for answer would be unionOfTwoLists and final_list could be unionList.
• I'd similarly echo @Jaime's comment that the name union is quite confusing. At first I was thinking your function was wrong because it allowed duplicated. Whether you keep the name or not, this is a good issue to address inn your docstring, to save future code readers confusion, which brings me to the next point
• You need some comments, at least a docstring for your function.
• Why don't you format your code so that the related if...else branches are closer together? They look as independent of one another as the other control statements, but they aren't. It's nice when the eye can see just from the form of the code which chunks are 'units' of a sort.
• Thanks man!! Sadly I can't accept two answers. Thumbs up for an amazing feedback! – python Sep 8 '15 at 17:41

What your code is doing is typically described as merging both lists. The word union sounds like the set operation, where repeated values should appear only once.

Assuming your interpretation is correct, you typically want to minimize the amount of work done in the inner loop of any algorithm. In your case, this is typically done by not handling the items of one list once the other is exhausted inside that loop, but afterwards.

Also, the typical way of merging is that, in case of a tie, the value from the first list goes into the final list first. This is mostly irrelevant for your case, but it is a good habit to write these things conforming to that norm, so that if you ever find yourself writing code for an indirect mergesort, you willt be less likely to make it non-stable by mistake.

while idx1 < len(list1) and idx2 < len(list2):
if list2[idx2] < list1[idx1]:
final_list.append(list2[idx2])
idx2 += 1
else:  # Ties are solved in favor of the first list
final_list.append(list1[idx1])
idx1 += 1
while idx1 < len(list1):
final_list.append(list1[idx1])
idx1 += 1
while idx2 < len(list2):
final_list.append(list2[idx2])
idx2 += 1


We are not supposed to use any built-in Python functions, but rather develop our own efficient algorithms.

You are not following the spec. len is a built-in function, range is a built-in class with many hidden functions, + is implemented as a hidden function, as > and < are. The only way to avoid using any built-in Python functions is not using Python.

The best solution to many problems is using as many Python built-ins as possible. The solution to this problem is simply:

def merge(list1, list2):
return sorted(list1 + list2)


This solution is way faster than yours, and the new list is now lazy, saving memory. Ironically, my function, that uses only 2 built-in functions (sorted and +) follows the spec more than yours that uses tens of such built-in functions.

• I can't agree. Merging two sorted lists is O(n+m) (n and m are the lengths of the lists). Concating the two and then sorting is obviously simpler but it must be at least O((n + m) * lg(n + m)) which will be bigger. Now, I know in the general case your solution is faster but I think the OP is learning about algorithms, and the merge operation of a mergesort is an important algorithm for beginners. – Boris the Spider Sep 8 '15 at 10:17
• @BoristheSpider Sorting a list composed of two increasing sequences is optimized and runs in O(N) time complexity. – Caridorc Sep 8 '15 at 11:13
• @BoristheSpider but I see your point about the learning experience. – Caridorc Sep 8 '15 at 11:14
• @Caridorc what is this algorithm that sorts in O(N) time? – spyr03 Sep 8 '15 at 16:42
• We are not supposed to use sort and '+' functions here. But thanks for your answer. – python Sep 8 '15 at 17:35