Sorting sequences

Factor handbook » The language » Collections » Sequence operations

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 all 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:

Sorting a sequence with common comparators:

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 all 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 ( seq quot: ( obj1 obj2 -- <=> ) -- sortedseq )

Sorting a sequence with common comparators:

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

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

natural-sort ( seq -- sortedseq )

sort-keys ( obj -- sortedseq )

sort-values ( obj -- sortedseq )