! Copyright (C) 2009 Richard Osborn. ! See http://factorcode.org/license.txt for BSD license. USING: kernel combinators combinators.short-circuit generalizations sequences arrays math fry ; IN: qsort : choose-pivot ( seq -- pivot ) 0 swap nth ; : insertion-sort ( seq -- ) 1 ! seq i over length 1 - ! seq i len- [ ! seq i 2dup swap nth 2over ! seq i key seq j [ 3dup { [ 2nip 0 > ] ! j > 0 ? [ 1 - swap nth < ] ! key < seq[j-1] ? } 3&& ] [ dup 1 - pick nth 2over swap set-nth ! seq[j-1] = 1 - ! j-1 ] while swap set-nth ! seq[j] = key 1 + ! seq i+ ] times ! seq i 2drop ! ; : qsort ( seq -- ) dup length 8 < [ insertion-sort ] [ dup choose-pivot '[ _ < ] partition [ qsort ] bi@ ] if ; recursive