# Autogenerated with DRAKON Editor 1.5

proc quick_sort { collection comparer } {
    set _next_item_ 15
    while { 1 } {
        if {$_next_item_ == 15} {
            set length [ llength $collection]
    
        #item 18
            set _sw_18 $length
            if {$_sw_18 == 0} {
                set _next_item_ 29
            } elseif {$_sw_18 == 1} {
                set _next_item_ 29
            } elseif {$_sw_18 == 2} {
                #item 34
                set first [ lindex $collection 0 ]
                set second [ lindex $collection 1 ]
                set _next_item_ 35
            } else {
                #item 40
                set half [ expr { $length / 2 } ]
                set median [ lindex $collection $half ]
                set left {}
                set right {}
                #item 410001
                set i 0
                set _next_item_ 410002
            }
        }
    
        if {$_next_item_ == 410002} {
            if {$i < $length} {
                
            } else {
                #item 52
                set left_sorted [ quick_sort $left $comparer ]
                set right_sorted [ quick_sort $right $comparer ]
                #item 53
                return [ concat $left_sorted [ list $median ] $right_sorted ]
            }
    
        #item 88
            if {$i == $half} {
                set _next_item_ 410003
            } else {
                #item 43
                set current [ lindex $collection $i ]
                set _next_item_ 44
            }
        }
    
        if {$_next_item_ == 44} {
            if {[ $comparer $current $median ] < 0} {
                #item 45
                lappend left $current
                set _next_item_ 410003
            } else {
                #item 46
                lappend right $current
                set _next_item_ 410003
            }
        }
    
        if {$_next_item_ == 410003} {
            incr i
            set _next_item_ 410002
            continue
        }
    
        if {$_next_item_ == 35} {
            if {[ $comparer $first $second ] < 0} {
                #item 36
                return $collection
            } else {
                #item 37
                return [ list $second $first ]
            }
        }
    
        if {$_next_item_ == 29} {
            return $collection
        }
    
    }
}

proc quick_sort_demo { } {
        #item 63
    set unsorted { the sooner we start this the better }
    set sorted { aa bb cc dd ee ff }
    set empty {}
    set flat { flat flat flat flat }
    #item 64
    set unsorted2 [ quick_sort $unsorted string_comparer ]
    set sorted2 [ quick_sort $sorted string_comparer ]
    set empty2 [ quick_sort $empty string_comparer ]
    set flat2 [ quick_sort $flat string_comparer ]
    #item 81
    puts $unsorted2
    puts $sorted2
    puts $empty2
    puts $flat2
    #item 90
    strings_are_sorted $unsorted2
    strings_are_sorted $sorted2
    strings_are_sorted $empty2
    strings_are_sorted $flat2
    return {}
    
}

proc string_comparer { left right } {
        #item 57
    return [ string compare $left $right ]
    
}

proc strings_are_sorted { array } {
    set _next_item_ 91
    while { 1 } {
        if {$_next_item_ == 91} {
            set length [ llength $array ]
            #item 700001
            set i 0
            set _next_item_ 700002
        }
    
        if {$_next_item_ == 700002} {
            if {$i < $length} {
                #item 72
                set current [ lindex $array $i ]
                #item 730001
                set j [ expr { $i + 1 } ]
                set _next_item_ 730002
            } else {
                return {}
            }
        }
    
        if {$_next_item_ == 730002} {
            if {$j < $length} {
                #item 76
                set after [ lindex $array $j ]
                set _next_item_ 92
            } else {
                #item 700003
                incr i
                set _next_item_ 700002
                continue
            }
        }
    
        if {$_next_item_ == 92} {
            set _sw_92 [ string compare $current $after ]
            if {$_sw_92 == -1} {
                set _next_item_ 730003
            } elseif {$_sw_92 == 0} {
                set _next_item_ 730003
            } elseif {$_sw_92 == 1} {
                #item 77
                error "Collection is not sorted:\n$array"
                return {}
            } else {
                error "Unexpected switch value: $_sw_92"
            }
        }
    
        if {$_next_item_ == 730003} {
            incr j
            set _next_item_ 730002
            continue
        }
    
    }
}

quick_sort_demo
