排序

merge_sort.py

def merge_sort(items):
    """Return a new sorted list (stable, O(n log n))."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # take the left one on ties: stable
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]


if __name__ == "__main__":
    data = [38, 27, 43, 3, 9, 82, 10]
    print(merge_sort(data))                  # [3, 9, 10, 27, 38, 43, 82]
    print(merge_sort(data) == sorted(data))  # True

python merge_sort.py