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

Question

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])

Answer 1

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

Answer 2

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!

Answer 3

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

Answer 4

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.

Readability

• 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.

Answer 5

I think if we set instead of the sort then it will be considered as a union in case of + in the case of the same elements in both lists it will just add the elements twice in final list