shit

from random import shuffle

#s1 = [
#        4,
#        1,
#        2,
#        3,
#        5,
#        8,
#        6,
#        7,
#]

s1 = range(15)
shuffle(s1)


def split_stacks(s1, tmp=None):
    stash = []
    tmp = tmp or []
    while s1:
        #print('source', s1)
        #print('stash', stash)
        #print('tmp', tmp)

        value = s1.pop()
        # top
        top = stash[-1] if stash else None
        if top is None or value < top:
            stash.append(value)
        else:
            tmp.append(value)
    return stash, tmp



ordered = []
tmp = []
stash = s1
while True:
    stash, tmp = split_stacks(stash, tmp=tmp)


    if len(stash) == 1:
        ordered.append(stash.pop())
        if not tmp:
            break
        stash = tmp
        tmp = []


print('done')
print(ordered)