Sort Libraries is a library of sort-related procedures for working on lists.

The library is inspired by Scheme's SRFI 132, and uses the same procedure API. The library provides procedures to sort, merge and work with sorted lists, and is useful particularly in cases where records or other structures must be ordered with custom comparison procedures.

statistics

list_binary_search (*is_lt, is_equal, lst, item, start_index, end_index*)

Returns the index of given item in list, or fails if item is not in list.

list_binary_search("<", "=", [1,1,2,3], 2) # => 3

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- is_equal
- a procedure of two arguments, succeeding if the first is "equal to" the second
- lst
- a list of items
- item
- to find in list
- start_index
- optional start index to search from (defaults to 1)
- end_index
- optional end index to search to (defaults to length of list)

list_delete_neighbour_dups (*is_equal, lst*)

Returns a new list without duplicate items from the given (sorted) list.

list_delete_neighbour_dups("=", [1,1,2,2,3]) # => [1,2,3]

Parameters:

- is_equal
- a procedure of two arguments, succeeding if the first is "equal to" the second
- lst
- a list of items

list_find_median (*is_lt, lst, nil, compute_mean*)

Returns the median element from given list.

- If the list is empty, returns the `nil` value.
- If the list has an odd number of elements, returns its middle element.
- Otherwise, returns the result of applying the `compute_mean` procedure to its two middle elements.

list_find_median("<", [1,2,3,4,5], 0) # => 3 list_find_median("<", [1,2,3,4], 0) # => 2.5

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- lst
- a list of items
- nil
- value to return for an empty list
- compute_mean
- optional procedure for computing mean of two middle elements, defaults to using `arithmetic_mean` from statistics.

list_is_sorted (*is_lt, lst*)

Succeeds if the given list is sorted.

list_is_sorted("<", [1,2,2,3]) # => succeeds

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- lst
- a list of items

list_merge (*is_lt, lst1, lst2*)

Returns a new ordered list consisting of the items in the two given lists.

list_merge("<", [1,3,5], [2,4]) # => [1,2,3,4,5]

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- lst1
- a list of items
- lst2
- a list of items

list_select (*is_lt, lst, k*)

Returns the kth smallest element. Fails if the list is smaller than k elements.

list_select("<", [4,1,2,5], 3) # => 4

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- lst
- a list of items
- k
- order index of element to return

list_separate (*is_lt, lst, k*)

Destructively modifies the list to place the smallest k items at the front.

list_separate("<", [4,1,2,5], 2) # list changed to => [1,2,5,4]

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- lst
- a list of items
- k
- number of elements to move

list_sort (*is_lt, lst*)

Destructively sorts the given list.

list_sort(">", [3,1,2]) # list changed to => [3,2,1]

Parameters:

- is_lt
- a procedure of two arguments, succeeding if the first is "less than" the second
- lst
- a list of items