Hackbright Code Challenges

Sort Sorted Lists: Solution

Sort Sorted Lists: Solution

Problem

Sort Sorted Lists

Whiteboard

Medium

Challenge

Easier

Concepts

Loops, Sorting

Download

sort-ab-solution.zip


This ends up being a merge — you can loop and look at the first item in both A and B. Whichever should get sorted first goes onto the sorted list. This is very similar to the merge stage of merge sort.

The runtime for this is O(a + b), where a and b are the lengths of lists a and b, respectively.

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

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

    # START SOLUTION

    out = []

    ia = 0  # index into list a
    ib = 0  # index into list b

    while ia < len(a) and ib < len(b):
        # Check current items in both lists:
        #  - if a < b, add a and increase ia
        #  - else      add b and increase ib

        if a[ia] < b[ib]:
            out.append(a[ia])
            ia += 1

        else:
            out.append(b[ib])
            ib += 1

    # One list could have things remaining; add any remaining items
    out.extend(a[ia:])
    out.extend(b[ib:])

    return out