`sort`

Sorting algorithms - sort a list ascending or descending, sort with a custom comparator function, sort by a key extractor, reverse a list, check if a list is already sorted, sort and deduplicate, find the top-k smallest elements (partial sort), and merge two sorted lists.

Load with: use sort

What this module does

sort provides a complete suite of sorting utilities all implemented as pure-ilusm bubble sort (for simplicity and correctness at small-to-medium sizes). All sort functions return a new list - the original is not mutated. For custom orderings supply a comparator that returns negative/zero/positive like a standard three-way compare.

Quick example

use sort

nums = [3, 1, 4, 1, 5, 9, 2, 6]

prn(srtup(nums))    # [1, 1, 2, 3, 4, 5, 6, 9]  ascending
prn(srtdn(nums))    # [9, 6, 5, 4, 3, 2, 1, 1]  descending
prn(srtrv(nums))    # reversed

# Sort by key
people = [{name: "Zoe", age: 25}, {name: "Alice", age: 30}]
by_name = srtky(people, \(p) p.name)  # [{name:"Alice"...}, {name:"Zoe"...}]

# Custom comparator
asc = srtby([3,1,2], \(a,b) a - b)

# Sorted check
prn(srtok([1,2,3]))   # tru
prn(srtdok([3,2,1]))  # tru (descending sorted check)

# Unique
prn(srtun(nums))      # [1, 2, 3, 4, 5, 6, 9]  sorted unique

# Top 3 smallest
prn(srttk(nums, 3))   # [1, 1, 2]

# Merge two sorted lists
prn(srtmg([1, 3, 5], [2, 4, 6]))  # [1, 2, 3, 4, 5, 6]

Functions

Sorting

srtup(xs) / sort.up(xs)

Sorts a list in ascending order using the default > comparator. Returns a new list.

srtdn(xs) / sort.dn(xs)

Sorts a list in descending order. Returns a new list.

srtby(xs, cmp) / sort.by(xs, cmp)

Sorts using a custom comparator cmp(a, b). Returns positive if a > b, negative if a < b, zero if equal.

srtky(xs, fn) / sort.key(xs, fn)

Sorts by a key extracted by fn(item). Compares keys with </>.

Inspection and transformation

srtrv(xs) / sort.rev(xs)

Reverses a list. Returns a new list.

srtok(xs) / sort.ok(xs)

Returns tru if the list is sorted in ascending order.

srtdok(xs)

Returns tru if the list is sorted in descending order.

srtun(xs) / sort.unq(xs)

Sorts ascending and removes duplicates. Returns a new unique sorted list.

Partial sort and merge

srttk(xs, n) / sort.top(xs, n)

Returns the n smallest elements in sorted order (partial selection sort). More efficient than full sort when n << len(xs).

srtmg(a, b) / sort.mrg(a, b)

Merges two sorted lists into one sorted list (merge step of merge sort).

Notes

All sort variants use bubble sort - O(n²) worst case, suitable for lists up to a few thousand elements.
Requires trl.