# SRFI 132 - Sort Libraries

The `(srfi 132)` library implements the the API for a full-featured sort toolkit.

See the [SRFI document](http://srfi.schemers.org/srfi-132/srfi-132.html) for more information.

- [`list-delete-neighbor-dups!`](#list-delete-neighbor-dups-1)
- [`list-delete-neighbor-dups`](#list-delete-neighbor-dups)
- [`list-merge!`](#list-merge-1)
- [`list-merge`](#list-merge)
- [`list-sort!`](#list-sort-1)
- [`list-sort`](#list-sort)
- [`list-sorted?`](#list-sorted)
- [`list-stable-sort!`](#list-stable-sort)
- [`list-stable-sort`](#list-stable-sort)
- [`vector-delete-neighbor-dups!`](#vector-delete-neighbor-dups-1)
- [`vector-delete-neighbor-dups`](#vector-delete-neighbor-dups)
- [`vector-find-median`](#vector-find-median)
- [`vector-find-median!`](#vector-find-median-1)
- [`vector-merge!`](#vector-merge-1)
- [`vector-merge`](#vector-merge)
- [`vector-select!`](#vector-select)
- [`vector-separate!`](#vector-separate)
- [`vector-sort!`](#vector-sort-1)
- [`vector-sort`](#vector-sort)
- [`vector-sorted?`](#vector-sorted)
- [`vector-stable-sort!`](#vector-stable-sort)
- [`vector-stable-sort`](#vector-stable-sort)

# list-delete-neighbor-dups

    (list-delete-neighbor-dups = lis)

This procedure does not alter its input list, but its result may share storage with the input list.

# list-delete-neighbor-dups!

    (list-delete-neighbor-dups! = lis)

This procedure mutates its input list in order to construct its result. It makes only a single, iterative, linear-time pass over its argument, using set-cdr!s to rearrange the cells of the list into the final result — it works "in place." Hence, any cons cell appearing in the result must have originally appeared in the input.

# list-merge

    (list-merge < lis1 lis2)

This procedure does not alter its inputs, and is allowed to return a value that shares a common tail with a list argument.

All four merge operations are stable: an element of the initial list `lis1` or vector `v1` will come before an equal-comparing element in the second list `lis2` or vector `v2` in the result.

# list-merge!

    (list-merge! < lis1 lis2)

This procedure makes only a single, iterative, linear-time pass over its argument lists, using `set-cdr!`s to rearrange the cells of the lists into the list that is returned — it works "in place." Hence, any cons cell appearing in the result must have originally appeared in an input. It returns the sorted input.

Additionally, `list-merge!` is iterative, not recursive — it can operate on arguments of arbitrary size without requiring an unbounded amount of stack space. The intent of this iterative-algorithm commitment is to allow the programmer to be sure that if, for example, `list-merge!` is asked to merge two ten-million-element lists, the operation will complete without performing some extremely (possibly twenty-million) deep recursion.

All four merge operations are stable: an element of the initial list `lis1` or vector `v1` will come before an equal-comparing element in the second list `lis2` or vector `v2` in the result.

# list-sort

    (list-sort < lis)

This procedure provides basic sorting.

# list-sort!

    (list-sort! < lis)

This procedure is a linear update operator and is allowed to alter the cons cells of the arguments to produce its results. A sorted list containing the same elements as `lis` is returned.

# list-sorted?

    (list-sorted? < lis)

Returns true iff the input list is in sorted order, as determined by `<`. Specifically, return `#f` iff there is an adjacent pair `... X Y ...` in the input list such that `Y < X` in the sense of `<`.

# list-stable-sort

    (list-stable-sort < lis)

Provides a stable sort.

# list-stable-sort!

    (list-stable-sort! < lis)

This procedure is a linear update operator and is allowed to alter the cons cells of the arguments to produce its results. A sorted list containing the same elements as `lis` is returned.

# vector-delete-neighbor-dups

    (vector-delete-neighbor-dups = v [ start [ end ] ])

This procedure does not alter its input vector, but rather newly allocates and returns a vector to hold the result.

# vector-delete-neighbor-dups!

    (vector-delete-neighbor-dups! = v [ start [ end ] ])

This procedure reuses its input vector to hold the answer, packing it into the index range [start, newend), where newend is the non-negative exact integer that is returned as its value. The vector is not altered outside the range [start, newend).

# vector-find-median

    (vector-find-median < v knil [ mean ])

This procedure does not alter its input vector, but rather newly allocates a vector to hold the intermediate result. Runs in O(n) time.

# vector-find-median!

    (vector-find-median! < v knil [ mean ])

This procedure reuses its input vector to hold the intermediate result, leaving it sorted, but is otherwise the same as vector-find-median. Runs in O(n ln n) time.

# vector-merge

    (vector-merge < v1 v2 [ start1 [ end1 [ start2 [ end2 ] ] ] ])

This procedure does not alter its inputs, and returns a newly allocated vector of length `(end1 - start1) + (end2 - start2)`.

All four merge operations are stable: an element of the initial list `lis1` or vector `v1` will come before an equal-comparing element in the second list `lis2` or vector `v2` in the result.

# vector-merge!

    (vector-merge! < to from1 from2 [ start [ start1 [ end1 [ start2 [ end2 ] ] ] ] ])

This procedure writes its result into vector `to`, beginning at index `start`, for indices less than `end`, which is defined as `start + (end1 - start1) + (end2 - start2)`. The target subvector `to[start, end)` may not overlap either of the source subvectors `from1[start1, end1]` and `from2[start2, end2]`. It returns an unspecified value.

All four merge operations are stable: an element of the initial list `lis1` or vector `v1` will come before an equal-comparing element in the second list `lis2` or vector `v2` in the result.

# vector-select!

    (vector-select! < v k [ start [ end ] ] )

This procedure returns the `k`th smallest element (in the sense of the `<` argument) of the region of a vector between `start` and `end`. Elements within the range may be reordered, whereas those outside the range are left alone. Runs in `O(n)` time.

# vector-separate!

    (vector-separate! < v k [ start [ end ] ] )

This procedure places the smallest `k` elements (in the sense of the `<` argument) of the region of a vector between `start` and `end` into the first `k` positions of that range, and the remaining elements into the remaining positions. Otherwise, the elements are not in any particular order. Elements outside the range are left alone. Runs in `O(n)` time. Returns an unspecified value.

# vector-sort

    (vector-sort < v [ start [ end ] ])

This procedure does not alter its inputs, but allocates a fresh vector as the result, of length `end - start`.

# vector-sort!

    (vector-sort! < v [ start [ end ] ])

Sort the data in-place and return an unspecified value.

# vector-sorted?

    (vector-sorted? < v [start [ end ] ])

Returns true iff the input vector is in sorted order, as determined by `<`. Specifically, return `#f` iff there is an adjacent pair `... X Y ...` in the input vector such that `Y < X` in the sense of `<`. The optional `start` and `end` range arguments restrict `vector-sorted?` to examining the indicated subvector.

# vector-stable-sort

    (vector-stable-sort < v [ start [ end ] ])

This procedure does not alter its inputs, but allocates a fresh vector as the result, of length `end - start`.

# vector-stable-sort!

    (vector-stable-sort! < v [ start [ end ] ])

Sorts the data in-place. (But note that `vector-stable-sort!` may allocate temporary storage proportional to the size of the input — there are no known `O(n lg n)` stable vector sorting algorithms that run in constant space.) Returns an unspecified value.