sort

Status: complete, though doesn't entirely detail the underlying implementation, since a great deal of this is mostly introductory Computer Science stuff.

Description: contains functions for sorting lists and `normal' vectors.

Note: for each argument named less?, this refers to a procedure of two arguments, which returns #t if the first argument is less than the second argument, else returns #f

Note: most of the documentation is from the `NEWS' file.

Note: we use both quicksort and mergesort, depending on whether we want to be stable or not. Consult a good book on algorithms if you have no idea what I mean.

Function: sorted? seq less?

C Function: SCM scm_sorted_p (SCM seq, SCM less)

Returns #t when the sequence argument seq is in non-decreasing order according to less? (that is, there is no adjacent pair `... x y ...' for which `(less? y x)').

Returns #f when the sequence contains at least one out-of-order pair. It is an error if the sequence is neither a list nor a vector.

Function: merge list1 list2 less?

C Function: SCM scm_merge (SCM list1, SCM list2, SCM less)

list1 and list2 are sorted lists. Returns the sorted list of all elements in list1 and list2.

Assume that the elements a and b1 in list1 and b2 in list2 are "equal" in the sense that (less? x y) --> #f for x, y in {a, b1, b2}, and that a < b1 in list1. Then a < b1 < b2 in the result. (Here "<" should read "comes before".)

Function: merge! list1 list2 less?

C Function: SCM scm_merge_x (SCM list1, SCM list2, SCM less)

Merges two lists, re-using the pairs of list1 and list2 to build the result. If the code is compiled, and less? constructs no new pairs, no pairs at all will be allocated. The first pair of the result will be either the first pair of list1 or the first pair of list2.

Function: sort sequence less?

C Function: SCM scm_sort (SCM sequence, SCM less)

Accepts either a list or a vector, and returns a new sequence which is sorted. The new sequence is the same type as the input. Always "(sorted? (sort sequence less?) less?)". The original sequence is not altered in any way. The new sequence shares its elements with the old one; no elements are copied.

Function: sort! sequence less

C Function: SCM scm_sort_x (SCM sequence, SCM less)

Returns its sorted result in the original boxes. No new storage is allocated at all. Proper usage: (set! slist (sort! slist <))

Function: stable-sort sequence less?

C Function: SCM scm_stable_sort (SCM sequence, SCM less)

Similar to sort but stable. That is, if "equal" elements are ordered a < b in the original sequence, they will have the same order in the result.

Function: stable-sort! sequence less?

C Function: SCM scm_stable_sort_x (SCM sequence, SCM less)

Similar to sort! but stable. Uses temporary storage when sorting vectors.

Function: sort-list lst less?

C Function: SCM scm_sort_list (SCM lst, SCM less)

A stable list sort.

Function: sort-list! lst less?

C Function: SCM scm_sort_list_x (SCM lst, SCM less)

A destructive, stable list sort.