list-sort, vector-sort - stable sorting of lists and vectors

LIBRARY

(import (rnrs))                     ;R6RS
(import (rnrs sorting))             ;R6RS

SYNOPSIS

(list-sort proc list)
(vector-sort proc vector)

DESCRIPTION

These procedures perform a stable sort of list or vector in ascending order according to proc. The procedure proc should accept two elements and return a true value when its first argument is strictly less than its second, and #f otherwise.
Time complexity
The sorting algorithm performs O(n lg n) calls to proc where n is the length of list or vector.
Side effects
The procedure proc should not have any side effects. The pairing of arguments and the sequencing of calls to proc are not specified. The sorting algorithm does not modify list or vector.

IMPLEMENTATION NOTES

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.

RETURN VALUES

Both of these procedures return a single value. The list-sort procedure returns a list, and vector-sort returns a vector.

The return value may be eq? to the argument when the argument is already sorted, and the list returned by list-sort may share structure with a tail of the original list.

If multiple returns occur from list-sort or vector-sort, the return values returned by earlier returns are not mutated.

EXAMPLES

(list-sort < '(3 5 2 1))     =>  (1 2 3 5)
(vector-sort < '#(3 5 2 1))  =>  #(1 2 3 5)

COMPATIBILITY

These procedures are unique to R6RS. Alternatives are available in SRFI-95 and SRFI-132.

ERRORS

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. In particular, proc should accept two arguments, which are elements from list or vector, and return one value.

SEE ALSO

vector-sort!(3scm)

STANDARDS

R6RS

HISTORY

These procedures first appeared in R6RS.

AUTHORS

This page is part of the scheme-manpages project. It includes materials from the RnRS documents. More information can be found at https://github.com/schemedoc/manpages/.

Markup created by unroff 1.0sc,    March 04, 2023.