# SRFI 132 - Sort Libraries

The `(srfi 132)`

library implements the the API for a full-featured sort toolkit.

See the SRFI document for more information.

`list-delete-neighbor-dups!`

`list-delete-neighbor-dups`

`list-merge!`

`list-merge`

`list-sort!`

`list-sort`

`list-sorted?`

`list-stable-sort!`

`list-stable-sort`

`vector-delete-neighbor-dups!`

`vector-delete-neighbor-dups`

`vector-find-median`

`vector-find-median!`

`vector-merge!`

`vector-merge`

`vector-select!`

`vector-separate!`

`vector-sort!`

`vector-sort`

`vector-sorted?`

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

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