I devised the following sorting algorithm while playing with Legos, based on the idea of always stacking smaller pieces on top of bigger pieces until you come across a piece that doesn't fit on either end of the stack.
My initial impression is that its best-case behavior is O(n) and its worst-case behavior is O(n^2) since it's similar to strand sort, but it's been so long since I've done algorithmic analysis in college that I have no idea what its average behavior is. It looks like it ought to be better than strand sort's average O(n^2), but I don't know how to prove it or what it is.
My implementation uses a linked list to allow insertions on both ends, but a deque would work just as well. The following is Python code for convenience of description, but the C++ version is more efficient.
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
