Nuts and Bolts

def sort_nuts_and_bolts(nuts, bolts):
    """Sort nuts and bolts in O(N log N) time"""
    def sort(nuts, bolts):
        if len(nuts) == 0:
            return []
        lnuts, rnuts, lbolts, rbolts = [], [], [], []
        nut = nuts.pop()
        bolt = None
        for b in bolts:
            if b == nut and not bolt:
                bolt = b
                pair = [(nut, b)]
            elif b <= nut:
                lbolts.append(b)
            else:
                rbolts.append(b)
        for n in nuts:
            if n <= bolt:
                lnuts.append(n)
            else:
                rnuts.append(n)
        return sort(lnuts, lbolts) + pair + sort(rnuts, rbolts)

    return zip(*sort(nuts, bolts))