1 import bisect, heapq 2  3 def sort(seq): 4     piles = [] 5     for x in seq: 6         new_pile = [x] 7         i = bisect.bisect_left(piles, new_pile) 8         if i != len(piles): 9             piles[i].insert(0, x)10         else:11             piles.append(new_pile)12     print "longest increasing subsequence has length =", len(piles)13 14     # priority queue allows us to retrieve least pile efficiently15     for i in xrange(len(seq)):16         small_pile = piles[0]17         seq[i] = small_pile.pop(0)18         if small_pile:19             heapq.heapreplace(piles, small_pile)20         else:21             heapq.heappop(piles)22     assert not piles23 24 foo = [4, 65, 2, 4, -31, 0, 99, 1, 83, 782, 1]25 sort(foo)26 print foo