list-sort, vector-sort - stable sorting of lists and vectors
(import (rnrs)) ;R6RS
(import (rnrs sorting)) ;R6RS
(list-sort proc list)
(vector-sort proc vector)
These procedures perform a stable sort of
order according to
should accept two elements and return a true value when its first
argument is strictly less than its second, and
- Time complexity
The sorting algorithm performs O(n lg n)
where n is the length of
- Side effects
should not have any side effects.
The pairing of arguments and the sequencing of calls to
are not specified.
The sorting algorithm does not modify
Quicksort cannot be used because it has worse time complexity than
what is required. Heapsort cannot be used either because it is not
stable. Merge sort satisfies all requirements and can be used, but
it is not the only option.
Both of these procedures return a single value.
procedure returns a list, and
returns a vector.
The return value may be
to the argument when the argument is already sorted, and the list
may share structure with a tail of the original list.
If multiple returns occur from
the return values returned by earlier returns are not mutated.
(list-sort < '(3 5 2 1)) => (1 2 3 5)
(vector-sort < '#(3 5 2 1)) => #(1 2 3 5)
These procedures are unique to R6RS. Alternatives are available in
SRFI-95 and SRFI-132.
This procedure can raise exceptions with the following condition types:
- &assertion (R6RS)
The wrong number of arguments was passed or an argument was outside its domain.
should accept two arguments, which are elements from
and return one value.
These procedures first appeared in R6RS.
This page is part of the
It includes materials from the RnRS documents.
More information can be found at
Markup created by unroff 1.0sc, March 04, 2023.