1 USING: help.markup help.syntax kernel math
5 ARTICLE: "sequences-sorting" "Sorting sequences"
6 "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."
8 "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."
10 "Sorting combinators all take comparator quotations with stack effect " { $snippet "( elt1 elt2 -- <=> )" } ", where the output value is one of the three " { $link "order-specifiers" } "."
12 "Sorting a sequence with a custom comparator:"
14 "Sorting a sequence with common comparators:"
23 ABOUT: "sequences-sorting"
26 { $values { "seq" sequence } { "quot" { $quotation ( obj1 obj2 -- <=> ) } } { "sortedseq" "a new sorted sequence" } }
27 { $description "Sorts the elements of " { $snippet "seq" } " into a new array using a stable sort." }
28 { $notes "The algorithm used is the merge sort." } ;
31 { $values { "seq" sequence } { "quot" { $quotation ( elt -- key ) } } { "sortedseq" "a new sorted sequence" } }
32 { $description "Sorts the elements of " { $snippet "seq" } " by applying " { $link compare } " with " { $snippet "quot" } " to each pair of elements in the sequence." } ;
35 { $values { "seq" sequence } { "quot" { $quotation ( elt -- key ) } } { "sortedseq" "a new sorted sequence" } }
36 { $description "Sorts the elements of " { $snippet "seq" } " by applying " { $link compare } " with " { $snippet "quot" } " to each pair of elements in the sequence and inverting the results." } ;
39 { $values { "obj" object } { "sortedseq" "a new sorted sequence" } }
40 { $description "Sorts the elements of " { $snippet "obj" } " (converting to an alist first if not a sequence), comparing first elements of pairs using the " { $link <=> } " word." } ;
43 { $values { "obj" object } { "sortedseq" "a new sorted sequence" } }
44 { $description "Sorts the elements of " { $snippet "obj" } " (converting to an alist first if not a sequence), comparing second elements of pairs using the " { $link <=> } " word." } ;
47 { $values { "seq" sequence } { "sortedseq" "a new sorted sequence" } }
48 { $description "Sorts a sequence of objects in natural order using the " { $link <=> } " word." } ;
51 { $values { "a" object } { "b" object } { "c" object } { "d" object } }
52 { $description "If " { $snippet "a" } " is greater than " { $snippet "b" } ", exchanges " { $snippet "a" } " with " { $snippet "b" } "." } ;
55 { $values { "quots" { $sequence { $quotation ( obj1 obj2 -- <=> ) } } } }
56 { $description "Generate a chained comparator using the specified " { $snippet "quots" } " sequence of comparators." } ;
59 { $values { "seq" sequence } { "n" integer } }
60 { $description "Outputs the index of the midpoint of " { $snippet "seq" } "." } ;
62 { <=> compare compare-with natural-sort sort-with inv-sort-with sort-keys sort-values } related-words