Sort Appendix

Both the SORT and INDEXED-SORT operators use the “introsort” algorithm which is worst case O(n * log(n)). This algorithm is considered a “comparison sort” because the algorithm deals only with ordering and relies on a passed-in comparison to read and evaluate the sequence elements against one another.

The implementation of the introsort algorithm, actually requires the Binary Predicate form, so if the result of evaluating the body returns a number “result”, it is converted to a Boolean by returning (result < 0) to the algorithm.

Comparison operators:

Examples:

TOKENS of “Foo bar BAZ” will return a list of 3 strings (”Foo” “bar” “BAZ”), these strings will be passed to the SORT operator which will evaluate STRCASECMP for each required comparison and returns (”bar” “BAZ” “Foo”).

In this example, we have used a case-sensitive sort, so the return value is (”BAZ” “Foo” “bar”) since lower-case letters come after upper-case ones.

This example gets the @name property of each element in @contents and then does a case-insensitive sort returning the ids. If @contents contains (foo bar baz) and foo is named “Foo”, bar is named “bar”, and baz is named “BAZ”, we would sort by the names and return the ids (baz foo bar) since their names sorted to (”BAZ” “Foo” “bar”).

This, more complicated example, demonstrates how to sort on a secondary index when two elements equivalent based upon the primary index. The index creates a list of 2 indices per element, and the comparisons refer to each index by either specifying ELEMENT position 0 or 1. It should be noted that, to support quantity pricing, price is actually represented as a list.