我在玩乐高积木时设计了以下排序算法，其理念是始终将较小的部分堆叠在较大的部分之上，直到您遇到一个不适合堆栈两端的部分。
我最初的印象是，它的最佳情况是 O(n)，最坏情况是 O(n^2)，因为它类似于链排序，但是自从我在大学里做过算法分析以来已经很久了我不知道它的平均行为是什么。看起来它应该比链排序的平均 O(n^2) 更好，但我不知道如何证明它或它是什么。
我的实现使用链表来允许在两端插入，但双端队列也可以。以下为方便描述的 Python 代码，但 C++ 版本效率更高。
import math
def merge(x, y):
output = []
xp = 0
yp = 0
if len(y) == 0 or len(x) == 0 or y[0] > x[-1]:
return x + y
elif x[0] > y[-1]:
return y + x
while xp < len(x) and yp < len(y):
if x[xp] < y[yp]:
output.append(x[xp])
xp = xp + 1
else:
output.append(y[yp])
yp = yp + 1
if xp < len(x):
output = output + x[xp:]
elif yp < len(y):
output = output + y[yp:]
return output
def treeMerge(heads, accum):
currHead = 0
while heads[currHead] is not None:
accum = merge(heads[currHead], accum)
heads[currHead] = None
currHead = currHead + 1
heads[currHead] = accum
return heads
def legoSort(input):
heads = [None] * int(math.log(len(input), 2) + 1)
accum = []
for i in input:
# can be <= for speed at the cost of sort stability
if len(accum) == 0 or i < accum[0]:
accum.insert(0,i)
elif i >= accum[-1]:
accum.append(i)
else:
heads = treeMerge(heads, accum)
accum = [i]
for i in heads:
if i is not None:
accum = merge(accum, i)
return accum