[jbr] 2013-02-09 - Here is a little thing from here: http://wordaligned.org/articles/patience-sort

Remember that tcl is a poor fit for data structures!

======
 source iter.tcl  ; # you'll need this http://wiki.tcl.tk/37704


 set data {
    x
    11 3 4 8 2 12 9 13 5 7 6 10 14
 }

 set n   [lindex $data 0]
 set seq [lrange $data 1 end]

 iterator psort { seq } {
    set tops {}

    foreach x $seq {
        set pile [expr [lsearch -real -bisect $tops $x] + 1]

        if { $pile < [llength $tops] } {
            lset tops $pile $x
        } else {
            lappend tops $x
        }

        yield [list $x $pile]
    }
 }

 proc lis { seq } {
    iterate { x pile } { psort $seq } {
        if { $pile > 0 } {
            set prev [expr [llength [dict get $piles [expr $pile-1]]]-1]
        } else {
            set prev {}
        }

        dict lappend piles $pile [list $prev $x]
    }


    set prev 0
    foreach pile [lreverse [dict keys $piles]] {
        lappend lis [lassign [lindex [dict get $piles $pile] $prev] prev]
    }
    lreverse $lis
 }

 puts [lis $seq]
======

<<categories>> Example