Sort Sorted Lists

Whiteboard

Medium

Challenge

Easier

Concepts

Loops, Sorting

Download

sort-ab.zip

Solution

Sort Sorted Lists: Solution

Given two already-sorted lists:

>>> a = [1, 3, 5, 7]
>>> b = [2, 6, 8, 10]

Write a function that returns a new list that is the sorted merge of both of them. For the above lists, our result would be:

>>> sort_ab(a, b)
[1, 2, 3, 5, 6, 7, 8, 10]

It would be easy to do this by just using Python’s built-in sort method, like this:

>>> out = a + b
>>> out.sort()

However, this would have the runtime of O(n log n), where n is the combined length of a and b. You can get a much better runtime by exploiting the fact that both of the input lists are already sorted.

Your challenge is to implement sort_ab where the runtime is O(a + b) (where a and b are the lengths of those lists, respectively).

We’ve given you a file, sortab.py, with a function, sort_ab:

def sort_ab(a, b):
    """Given already-sorted lists, `a` and `b`, return sorted list of both.

    You may not use sorted() or .sort().
    """

However, this is unimplemented. Write it.