boramalper.py 文件源码

def lazysort(l: list) -> typing.Iterator:
    # Stage 1
    stack = []
    current_list = iter(l)
    sentinel = object()
    first = next(current_list, sentinel)
    while first is not sentinel:
        sortedish, surplus = dropsort(itertools.chain((first,), current_list))
        stack.append(sortedish)
        current_list = surplus
        first = next(current_list, sentinel)

    # Stage 2
    if len(stack) < 2:  # the case where the list `l` is already sorted
        return iter(l)

    cur = heapq.merge(stack.pop(), stack.pop())
    while stack:
        cur = heapq.merge(cur, stack.pop())

    return cur