scry2.py

from __future__ import division, print_function

from random import shuffle

def makedeck(ncards):
    deck = range(ncards)
    shuffle(deck)
    return deck

def inorder(deck):
    for i, j in enumerate(deck):
        if i != j:
            return False
    return True

def bubble_scry_sort(deck):
    n = 0
    nordered = 0
    ncards = len(deck)
    
    while True:
        n += 1
        toptwo = deck[:2]
        rest = deck[2:]

        toptwo.sort()

        if toptwo[0] == toptwo[1] - 1:
            nordered += 1
        else:
            nordered = 0

        if nordered >= ncards and toptwo == [0, 1]:
            assert inorder(deck)
            break

        if toptwo[1] == ncards - 1:
            deck = rest + toptwo
        else:
            rest.insert(0, toptwo[1])
            rest.append(toptwo[0])
            deck = rest

    return n

def my_scry_sort(deck):
    n = 0
    lookingfor = 1

    while True:
        n += 1

        toptwo = deck[:2]
        rest = deck[2:]

        if lookingfor == len(deck) and toptwo == [0, 1]:
            assert inorder(deck)
            break

        toptwo.sort()

        if lookingfor in toptwo:
            if toptwo[0] == lookingfor - 1:
                lookingfor += 1
            else:
                toptwo.remove(lookingfor)
                deck = [lookingfor] + rest + toptwo
                continue

        deck = rest + toptwo

    return n

deck = makedeck(60)
nscry = my_scry_sort(deck)
nbubble = bubble_scry_sort(deck)
print(nscry, nbubble)