IN: sorting
ARTICLE: "sequences-sorting" "Sorting sequences"
+"The " { $vocab-link "sorting" } " vocabulary implements the merge-sort algorithm. It runs in " { $snippet "O(n log n)" } " time, and is a " { $emphasis "stable" } " sort, meaning that the order of equal elements is preserved."
+$nl
+"The algorithm only allocates two additional arrays, both the size of the input sequence, and uses iteration rather than recursion, and thus is suitable for sorting large sequences."
+$nl
"Sorting combinators all take comparator quotations with stack effect " { $snippet "( elt1 elt2 -- <=> )" } ", where the output value is one of the three " { $link "order-specifiers" } "."
$nl
"Sorting a sequence with a custom comparator:"
] unit-test
[ ] [ { 1 2 } [ 2drop 1 ] sort drop ] unit-test
+
+! Is it a stable sort?
+[ t ] [ { { 1 "a" } { 1 "b" } { 1 "c" } } dup sort-keys = ] unit-test
+
+[ { { 1 "a" } { 1 "b" } { 1 "c" } { 1 "e" } { 2 "d" } } ]
+[ { { 1 "a" } { 1 "b" } { 1 "c" } { 2 "d" } { 1 "e" } } sort-keys ] unit-test
{ to2 array-capacity } ;
: dump ( from to seq accum -- )
- #! Optimize common case where to - from = 1.
- >r >r 2dup swap - 1 =
- [ drop r> nth-unsafe r> push ]
- [ r> <slice> r> push-all ]
- if ; inline
+ #! Optimize common case where to - from = 1, 2, or 3.
+ >r >r 2dup swap - dup 1 =
+ [ 2drop r> nth-unsafe r> push ] [
+ dup 2 = [
+ 2drop dup 1+
+ r> [ nth-unsafe ] curry bi@
+ r> [ push ] curry bi@
+ ] [
+ dup 3 = [
+ 2drop dup 1+ dup 1+
+ r> [ nth-unsafe ] curry tri@
+ r> [ push ] curry tri@
+ ] [
+ drop r> subseq r> push-all
+ ] if
+ ] if
+ ] if ; inline
: l-elt [ from1>> ] [ seq>> ] bi nth-unsafe ; inline
: r-elt [ from2>> ] [ seq>> ] bi nth-unsafe ; inline
: dump-r [ [ from2>> ] [ to2>> ] [ seq>> ] tri ] [ accum>> ] bi dump ; inline
: l-next [ [ l-elt ] [ [ 1+ ] change-from1 drop ] bi ] [ accum>> ] bi push ; inline
: r-next [ [ r-elt ] [ [ 1+ ] change-from2 drop ] bi ] [ accum>> ] bi push ; inline
-: decide [ [ l-elt ] [ r-elt ] bi ] dip call +lt+ eq? ; inline
+: decide [ [ l-elt ] [ r-elt ] bi ] dip call +gt+ eq? ; inline
: (merge) ( merge quot -- )
- over l-done? [ drop dump-r ] [
- over r-done? [ drop dump-l ] [
+ over r-done? [ drop dump-l ] [
+ over l-done? [ drop dump-r ] [
2dup decide
- [ over l-next ] [ over r-next ] if
+ [ over r-next ] [ over l-next ] if
(merge)
] if
] if ; inline
! See http://factorcode.org/license.txt for BSD license.
USING: io.files io.encodings.ascii sequences generalizations
math.parser combinators kernel memoize csv symbols summary
-words accessors math.order sorting ;
+words accessors math.order binary-search ;
IN: usa-cities
SINGLETONS: AK AL AR AS AZ CA CO CT DC DE FL GA HI IA ID IL IN