1、有个大小不同的杯子和与之匹配的n个杯盖, 你可以尝试一个杯子和一个杯盖是否匹配, 尝试结果有三种：（1）杯子太大；（2）匹配成功；（3）杯盖太大. 除此之外，无法直接比较杯子与杯子之间的大小关系，也无法直接比较杯盖和杯盖之间的大小关系. 请设计一个分治算法完成所有杯子和杯盖的匹配, 算法的时间复杂性用匹配尝试的次数来衡量。请写出（1）算法设计的思路，包括边界条件、Divide、Conquer和Merge的基本过程；（2）算法的伪代码；（3）算法的时间复杂度。

1. 算法设计思路：
首先，我们需要找到一个杯子和一个杯盖进行匹配，然后根据匹配结果将所有杯子和杯盖分成三个部分：比杯子大的、匹配成功的、比杯盖大的。然后，对于比杯子大的和比杯盖大的部分，分别递归调用该算法，直到只剩下一个杯子和一个杯盖，或者某一部分为空。最后，将所有匹配成功的杯子和杯盖合并起来即可。

2. 算法伪代码：

match(cups, lids):
    if len(cups) == 1 and len(lids) == 1:
        if cups[0] == lids[0]:
            return [(cups[0], lids[0])]
        else:
            return []
    if len(cups) == 0 or len(lids) == 0:
        return []
    pivot = cups[0]
    larger_cups = []
    smaller_cups = []
    match_cups = []
    larger_lids = []
    smaller_lids = []
    match_lids = []
    for lid in lids:
        if lid < pivot:
            smaller_lids.append(lid)
        elif lid == pivot:
            match_lids.append(lid)
        else:
            larger_lids.append(lid)
    for cup in cups:
        if cup < pivot:
            smaller_cups.append(cup)
        elif cup == pivot:
            match_cups.append(cup)
        else:
            larger_cups.append(cup)
    matches = []
    matches.extend(match(match_cups, match_lids))
    matches.extend(match(larger_cups, larger_lids))
    matches.extend(match(smaller_cups, smaller_lids))
    return matches

3. 时间复杂度：
假设杯子和杯盖的数量都为n，每次匹配需要尝试一次，那么时间复杂度为O(nlogn)。