Sorting sequences
Factor handbook » The language » Collections » Sequence operations

Prev:Treating sequences as stacks
Next:Binary search


The sorting vocabulary implements the merge-sort algorithm. It runs in O(n log n) time, and is a stable sort, meaning that the order of equal elements is preserved.

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.

Sorting combinators take comparator quotations with stack effect ( elt1 elt2 -- <=> ), where the output value is one of the three Ordering specifiers.

Sorting a sequence with a custom comparator:
sort-with ( seq quot: ( obj1 obj2 -- <=> ) -- sortedseq )


Sorting a sequence with common comparators:
sort ( seq -- sortedseq )

inv-sort ( seq -- sortedseq )

sort-by ( seq quot: ( elt -- key ) -- sortedseq )

inv-sort-by ( seq quot: ( elt -- key ) -- sortedseq )

sort-keys ( obj -- sortedseq )

sort-values ( obj -- sortedseq )