迭代器自合并的排序实现对应哪种已知排序算法？

现有一种排序实现逻辑：只要列表未排序，就持续将其替换为自身迭代器与自身合并后的结果。请问该实现是否等价于某类常见排序算法（仅实现方式特殊），还是一种全新的排序算法？

测试代码 #

from random import shuffle
from heapq import merge
from itertools import pairwise

# 创建测试数据
a = list(range(100))
shuffle(a)

# 排序逻辑
while any(x > y for x, y in pairwise(a)):
    it = iter(a)
    a = list(merge(it, it))

print(a)

标准merge实现（排除heapq.merge细节影响） #

def merge(xs, ys):
    none = object()
    x = next(xs, none)
    y = next(ys, none)
    while (x is not none) and (y is not none):
        if x <= y:
            yield x
            x = next(xs, none)
        else:
            yield y
            y = next(ys, none)
    if x is not none:
        yield x
    if y is not none:
        yield y
    yield from xs
    yield from ys

结论与分析 #

这个实现并非全新算法，本质是冒泡排序的一种变体，只是用迭代器合并的特殊写法包装了冒泡排序的核心逻辑：

1. 单次merge操作的本质
   因为it是同一个列表的迭代器，merge(it, it)的执行过程等价于对列表做一次冒泡遍历：

   • 每次取迭代器的相邻两个元素比较，输出较小的那个，把较大的元素留在后续步骤中继续和下一个元素比较
   • 最终会把当前未排序部分的最大元素逐步"推"到未排序段的末尾，和冒泡排序每次遍历将最大元素挪到正确位置的逻辑完全一致

2. 循环逻辑的等价性
   循环条件any(x > y for x, y in pairwise(a))用于检查列表是否存在逆序对（即未完全排序），这和冒泡排序中"只要遍历过程中有交换发生就继续循环"的终止条件效果完全相同——都是直到列表完全有序才停止。

举个直观例子：

• 初始列表[4,3,2,1]，第一次merge后得到[3,2,1,4]（最大元素4被挪到末尾）
• 第二次merge后得到[2,1,3,4]（次大元素3被挪到正确位置）
• 第三次merge后得到[1,2,3,4]，排序完成
  这完全就是冒泡排序的典型执行流程。

内容的提问来源于stack exchange，提问作者no comment