list-sort(3scm) Scheme Programmer's Manual list-sort(3scm)

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 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.

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. 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.

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

vector-sort!(3scm)

R6RS

These procedures first appeared in R6RS.

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

2023-01-25