sort
Sorting vectors with the default or your own comparison, binary search, and a dozen sorting algorithms to learn from.
import sort
The sort package orders a Vector and searches one that is already in order. For most work two functions are enough: Sort for numbers and strings, and SortBy when you decide yourself what "smaller" means, students by their marks for instance. Every function is generic, so it works for any element type that supports <, or for any type at all with a comparison of your own. For containers that stay sorted as you add to them (an ordered map, a priority queue) see collections; for the median and percentiles of numbers see stats.
The functions sort the vector in place. Sorted and SortedBy return a sorted copy instead and leave the original alone; free the copy when you are done with it. The functions named after an algorithm (quick, merge, bubble and the rest) all give the same order and are here mostly for teaching and comparing; Sort is an introsort, which stays fast on any input.
What people get wrong:
- Assuming the order of equal elements is kept.
Sort,SortDesc,SortByandSortIndexare not stable. UseStableSortBywhen it matters. - Using
SortByon data with few distinct keys. It is a plain quick sort, and when many elements compare equal (sorting 100,000 orders by a status with three values) it slows down to quadratic time.StableSortByis a merge sort and stays fast there. - Searching an unsorted vector.
BinarySearch,LowerBoundandUpperBoundreturn wrong answers without any error when the vector is not sorted the same way. - Calling
MinorMaxon an empty vector. They read element 0 and stop the program.
Sort records by several fields
Real data is a vector of structs, and the order has more than one rule: team first, then the highest salary, then the name. Write those rules in one comparison function that returns true when a should come before b, and pass it to SortBy. Compare the first field, and only when it is equal move on to the next. To sort descending on a field, swap the comparison for that field only.
import sort
struct Employee:
pub name: str = ""
pub team: str = ""
pub salary: int = 0
end
func show(staff: Vector<Employee>):
each e in staff:
println " " + e.team, e.name, e.salary
end
end
func main:
mut staff := Vector {} as Vector<Employee>
defer staff.Free()
staff.Push(Employee { name = "Sara", team = "web", salary = 5200 })
staff.Push(Employee { name = "Omid", team = "data", salary = 6100 })
staff.Push(Employee { name = "Leila", team = "web", salary = 6100 })
staff.Push(Employee { name = "Babak", team = "data", salary = 4800 })
staff.Push(Employee { name = "Nima", team = "web", salary = 5200 })
by_team := (a: Employee, b: Employee):
if a.team != b.team: ret a.team < b.team end
if a.salary != b.salary: ret a.salary > b.salary end
ret a.name < b.name
end
sort.SortBy(staff, by_team)
println "team, then highest salary, then name:"
show(staff)
cheapest := sort.SortedBy(staff, (a: Employee, b: Employee): ret a.salary < b.salary end)
println "lowest paid:", cheapest.Get(0).name
println "still sorted by team:", sort.IsSortedBy(staff, by_team)
endSortBy does not promise to keep equal elements in their old order, which is why the comparison above goes all the way down to the name: with a full tie-break the result is the same however the sort works. SortedBy returns a sorted copy and leaves the original order alone. IsSortedBy checks an order, which is handy in a test or before a binary search.
Sort by one column after another
A table that the user sorts by date and then by status should show each status group still in date order. StableSortBy keeps equal elements in the order they arrived, so sorting by the secondary key first and the primary key second gives exactly that. It is a merge sort: it always takes n log n steps and needs a second buffer the size of the vector.
import sort
struct Order:
pub id: int = 0
pub status: str = ""
pub placed: str = ""
end
func main:
mut orders := Vector {} as Vector<Order>
defer orders.Free()
orders.Push(Order { id = 1041, status = "shipped", placed = "2026-10-03" })
orders.Push(Order { id = 1042, status = "pending", placed = "2026-10-01" })
orders.Push(Order { id = 1043, status = "shipped", placed = "2026-09-28" })
orders.Push(Order { id = 1044, status = "pending", placed = "2026-10-05" })
orders.Push(Order { id = 1045, status = "cancelled", placed = "2026-10-02" })
orders.Push(Order { id = 1046, status = "pending", placed = "2026-09-30" })
sort.StableSortBy(orders, (a: Order, b: Order): ret a.placed < b.placed end)
sort.StableSortBy(orders, (a: Order, b: Order): ret a.status < b.status end)
each o in orders:
println o.status, o.placed, o.id
end
endDates written as YYYY-MM-DD sort correctly as plain text, which is why the example compares them with <. The same trick fails for D/M/YYYY.
Rank one list by another
When the data lives in parallel vectors, such as names, scores and wins, sorting one of them would break the link with the others. SortIndex and SortIndexDesc sort a vector of positions instead and leave the data where it is; you then read every vector through those positions. The keys must be a Vector<f64> and both vectors are passed by reference, so declare them with mut. Fill the positions with 0 to n-1 first.
import sort
func main:
players := ["Ali", "Sara", "Reza", "Mina", "Kaveh"]
mut scores := Vector {} as Vector<f64>
mut wins := Vector {} as Vector<int>
mut order := Vector {} as Vector<int>
defer scores.Free()
defer wins.Free()
defer order.Free()
each s in [72.5, 91.0, 64.0, 88.5, 91.5]:
scores.Push(s)
end
each w in [3, 7, 2, 6, 8]:
wins.Push(w)
end
repeat players.Len() in i:
order.Push(i)
end
sort.SortIndexDesc(order, scores)
println "rank player score wins"
each rank, i in order:
println rank + 1, players[i], scores.Get(i), wins.Get(i)
end
ranked := sort.Sorted(scores)
println "median score:", ranked.Get(ranked.Len() / 2)
println "best:", sort.Max(scores), "worst:", sort.Min(scores)
endSearch a sorted vector
Once a vector is sorted, finding things in it is fast. LowerBound gives the first position not below a value and UpperBound the first position above it, so the two together give a price range, the count of one value, or the place where a new value keeps the order. BinarySearch returns the index of a value or -1. All three assume the vector is already sorted; on an unsorted vector they return wrong answers without any error.
import sort
func main:
mut prices := Vector {} as Vector<int>
defer prices.Free()
each p in [120, 45, 300, 99, 45, 210, 150, 80]:
prices.Push(p)
end
sort.Sort(prices)
println "sorted:", prices
lo := sort.LowerBound(prices, 80)
hi := sort.UpperBound(prices, 150)
println "between 80 and 150:", hi - lo, "items"
repeat lo to hi - 1 in i:
print prices.Get(i), ""
end
println ""
println "how many cost 45:", sort.UpperBound(prices, 45) - sort.LowerBound(prices, 45)
each fresh in [100, 10, 500]:
println "a new price of", fresh, "keeps the order at index", sort.LowerBound(prices, fresh)
end
println "index of 210:", sort.BinarySearch(prices, 210), "index of 211:", sort.BinarySearch(prices, 211)
endDistinct words and custom orders for strings
Sorting puts equal values next to each other, so removing duplicates is one pass that skips a word equal to the last one kept. SortBy with a lambda gives any other order, here the longest words first and alphabetical among equal lengths. SortDesc sorts in reverse.
import sort
import str
func main:
text := "the quick fox and the lazy dog and the cat"
mut words := str.Fields(text)
defer words.Free()
sort.Sort(words)
mut unique := Vector {} as Vector<str>
defer unique.Free()
each w in words:
if unique.Len() == 0 or unique.Get(unique.Len() - 1) != w:
unique.Push(w)
end
end
println unique.Len(), "distinct words:", unique
sort.SortBy(unique, (a: str, b: str):
if a.Len() != b.Len(): ret a.Len() > b.Len() end
ret a < b
end)
println "longest first:", unique
sort.SortDesc(words)
println "first word in reverse order:", words.Get(0)
endPersian alphabetical order
Sort compares strings byte by byte, which is the order of Unicode code points. For Persian that order is wrong: پ, چ, ژ, ک and گ were added to Unicode after the Arabic letters and sort after و, and ه comes before و. A comparison that looks each letter up in the Persian alphabet fixes it.
import sort
import str
const ALPHABET := "آابپتثجچحخدذرزژسشصضطظعغفقکگلمنوهی"
func rank(letter: str): int:
i := str.IndexOf(ALPHABET, letter)
if i < 0: ret 1000 end
ret i
end
func persian_less(a: str, b: str): bool:
mut i := 0
until i < a.Len() and i < b.Len():
ra := rank(a.Substr(i, 2))
rb := rank(b.Substr(i, 2))
if ra != rb: ret ra < rb end
i += 2
end
ret a.Len() < b.Len()
end
func main:
mut names := Vector {} as Vector<str>
defer names.Free()
each n in ["هما", "پریسا", "وحید", "آرش", "ژاله", "گلناز", "بابک", "چکاوک", "زهرا", "کاوه", "یاسمن", "حسن"]:
names.Push(n)
end
mut by_bytes := sort.Sorted(names)
defer by_bytes.Free()
println "Sort: ", by_bytes
sort.SortBy(names, (a: str, b: str): ret persian_less(a, b) end)
println "alphabet: ", names
endThe comparison reads two bytes at a time, which is right for Persian letters only. Names with spaces, the zero-width non-joiner or Latin letters need a fuller comparison that walks the text letter by letter.
| Job | Use |
|---|---|
| Numbers or strings, ascending | Sort, or Sorted for a copy |
| Descending | SortDesc |
| Structs or your own order | SortBy, SortedBy |
| Keep ties in order, or few distinct keys | StableSortBy |
| Keep parallel vectors together | SortIndex, SortIndexDesc |
| Find in a sorted vector | BinarySearch, LowerBound, UpperBound |
| Check an order | IsSorted, IsSortedBy |
Functions
Swap
func Swap<T>(v: Vector<T>, i: int, j: int)import sort
func main:
mut numbers := Vector {} as Vector<int>
defer numbers.Free()
each n in [5, 3, 9, 1, 7]:
numbers.Push(n)
end
println sort.IsSorted(numbers)
ordered := sort.Sorted(numbers)
println ordered, numbers
sort.Sort(numbers)
println numbers, sort.IsSorted(numbers)
sort.SortDesc(numbers)
println numbers
sort.Reverse(numbers)
println numbers, sort.Min(numbers), sort.Max(numbers)
sort.Swap(numbers, 0, 4)
println numbers
endSortBy
func SortBy<T>(v: Vector<T>, less: func(T, T): bool)less; less(a, b) has to return true when a should come before b. It is a quick sort and not stable, and it becomes slow when many elements compare equal; use StableSortBy then.import sort
struct Student:
pub name: str = ""
pub mark: int = 0
end
func main:
mut class := Vector {} as Vector<Student>
defer class.Free()
class.Push(Student { name = "Sara", mark = 18 })
class.Push(Student { name = "Ali", mark = 15 })
class.Push(Student { name = "Reza", mark = 18 })
class.Push(Student { name = "Maryam", mark = 20 })
higher := (a: Student, b: Student): ret a.mark > b.mark end
sort.StableSortBy(class, higher)
each s in class:
print s.name, ""
end
println ""
println sort.IsSortedBy(class, higher)
lower := (a: Student, b: Student): ret a.mark < b.mark end
ascending := sort.SortedBy(class, lower)
println ascending.Get(0).name
sort.SortBy(class, lower)
println class.Get(0).name
endStableSortBy
func StableSortBy<T>(v: Vector<T>, less: func(T, T): bool)SortBy, but equal elements keep the order they were in; in the example Sara stays before Reza because she came first. A merge sort: n log n on any input, with a temporary copy of the vector.The example for this item is shown with the ones above: sort-SortBy.salam
SortedBy
func SortedBy<T>(v: Vector<T>, less: func(T, T): bool): Vector<T>SortBy, so not stable). The original is unchanged.The example for this item is shown with the ones above: sort-SortBy.salam
IsSortedBy
func IsSortedBy<T>(v: Vector<T>, less: func(T, T): bool): boolThe example for this item is shown with the ones above: sort-SortBy.salam
BucketSort
func BucketSort(v: Vector<int>)import sort
func main:
repeat 3 in round:
mut v := Vector {} as Vector<int>
defer v.Free()
each n in [170, 45, 75, 90, 802, 24, 2, 66]:
v.Push(n)
end
if round == 0:
sort.RadixSort(v)
else round == 1:
sort.CountingSort(v)
else:
sort.BucketSort(v)
end
println v
end
endCountingSort
func CountingSort(v: Vector<int>)The example for this item is shown with the ones above: sort-IntSorts.salam
RadixSort
func RadixSort(v: Vector<int>)The example for this item is shown with the ones above: sort-IntSorts.salam
PancakeSort
func PancakeSort<T>(v: Vector<T>)import sort
func main:
data := [9, 4, 7, 1, 8, 2, 6, 3, 5, 0]
repeat 13 in round:
mut v := Vector {} as Vector<int>
each n in data:
v.Push(n)
end
switch round:
0: sort.QuickSort(v) break end
1: sort.MergeSort(v) break end
2: sort.HeapSort(v) break end
3: sort.InsertionSort(v) break end
4: sort.BinaryInsertionSort(v) break end
5: sort.SelectionSort(v) break end
6: sort.BubbleSort(v) break end
7: sort.ShellSort(v) break end
8: sort.CombSort(v) break end
9: sort.CocktailSort(v) break end
10: sort.GnomeSort(v) break end
11: sort.OddEvenSort(v) break end
12: sort.PancakeSort(v) break end
end
print sort.IsSorted(v), ""
v.Free()
end
println ""
mut d := Vector {} as Vector<int>
defer d.Free()
each n in data:
d.Push(n)
end
sort.IntroSort(d)
println d
endCombSort
func CombSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
BubbleSort
func BubbleSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
BinarySearch
func BinarySearch<T>(v: Vector<T>, x: T): intx in a sorted vector by binary search, or returns minus one when it is not there. With duplicates it returns one of their positions, not necessarily the first; use LowerBound for the first.import sort
func main:
mut numbers := Vector {} as Vector<int>
defer numbers.Free()
each n in [1, 3, 3, 3, 7, 9]:
numbers.Push(n)
end
println sort.BinarySearch(numbers, 7), sort.BinarySearch(numbers, 4)
println sort.LowerBound(numbers, 3), sort.UpperBound(numbers, 3)
endLowerBound
func LowerBound<T>(v: Vector<T>, x: T): intx: where x would be inserted to keep the vector sorted.The example for this item is shown with the ones above: sort-BinarySearch.salam
UpperBound
func UpperBound<T>(v: Vector<T>, x: T): intx. The distance between the upper and the lower bound is how many times x occurs.The example for this item is shown with the ones above: sort-BinarySearch.salam
SortIndex
func SortIndex(idx &: Vector<int>, keys &: Vector<f64>)idx by keys (a Vector<f64>) in ascending order. Use it when several vectors share an order and you want to see all of them sorted together. Not stable.import sort
func main:
names := ["Tehran", "Shiraz", "Tabriz"]
mut population := Vector {} as Vector<f64>
mut order := Vector {} as Vector<int>
defer population.Free()
defer order.Free()
population.Push(8.7)
population.Push(1.6)
population.Push(1.65)
repeat 3 in i:
order.Push(i)
end
sort.SortIndex(order, population)
each i in order:
print names[i], ""
end
println ""
sort.SortIndexDesc(order, population)
each i in order:
print names[i], ""
end
println ""
endSortIndexDesc
func SortIndexDesc(idx &: Vector<int>, keys &: Vector<f64>)SortIndex, descending; it sorts ascending and reverses, so tied keys come out in reverse.The example for this item is shown with the ones above: sort-SortIndex.salam
OddEvenSort
func OddEvenSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
GnomeSort
func GnomeSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
SelectionSort
func SelectionSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
HeapSort
func HeapSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
MergeSort
func MergeSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
ShellSort
func ShellSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
InsertionSort
func InsertionSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
BinaryInsertionSort
func BinaryInsertionSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
IntroSort
func IntroSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
IsSorted
func IsSorted<T>(v: Vector<T>): boolThe example for this item is shown with the ones above: sort-Sort.salam
Reverse
func Reverse<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Sort.salam
Min
func Min<T>(v: Vector<T>): TThe example for this item is shown with the ones above: sort-Sort.salam
Max
func Max<T>(v: Vector<T>): TThe example for this item is shown with the ones above: sort-Sort.salam
Sort
func Sort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Sort.salam
SortDesc
func SortDesc<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Sort.salam
Sorted
func Sorted<T>(v: Vector<T>): Vector<T>The example for this item is shown with the ones above: sort-Sort.salam
QuickSort
func QuickSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam
CocktailSort
func CocktailSort<T>(v: Vector<T>)The example for this item is shown with the ones above: sort-Algorithms.salam