Standard library · Numbers and collections

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, SortBy and SortIndex are not stable. Use StableSortBy when it matters.
  • Using SortBy on 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. StableSortBy is a merge sort and stays fast there.
  • Searching an unsorted vector. BinarySearch, LowerBound and UpperBound return wrong answers without any error when the vector is not sorted the same way.
  • Calling Min or Max on 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.

sort-guide-records.salam
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)
end
Outputteam, then highest salary, then name: data Omid 6100 data Babak 4800 web Leila 6100 web Nima 5200 web Sara 5200 lowest paid: Babak still sorted by team: true

SortBy 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.

sort-guide-stable.salam
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
end
Outputcancelled 2026-10-02 1045 pending 2026-09-30 1046 pending 2026-10-01 1042 pending 2026-10-05 1044 shipped 2026-09-28 1043 shipped 2026-10-03 1041

Dates 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.

sort-guide-leaderboard.salam
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)
end
Outputrank player score wins 1 Kaveh 91.5 8 2 Sara 91 7 3 Mina 88.5 6 4 Ali 72.5 3 5 Reza 64 2 median score: 88.5 best: 91.5 worst: 64

Search 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.

sort-guide-ranges.salam
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)
end
Outputsorted: [45, 45, 80, 99, 120, 150, 210, 300] between 80 and 150: 4 items 80 99 120 150 how many cost 45: 2 a new price of 100 keeps the order at index 4 a new price of 10 keeps the order at index 0 a new price of 500 keeps the order at index 8 index of 210: 6 index of 211: -1

Distinct 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.

sort-guide-unique.salam
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)
end
Output7 distinct words: ["and", "cat", "dog", "fox", "lazy", "quick", "the"] longest first: ["quick", "lazy", "and", "cat", "dog", "fox", "the"] first word in reverse order: the

Persian 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.

sort-guide-persian.salam
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
end
OutputSort: ["آرش", "بابک", "حسن", "زهرا", "هما", "وحید", "پریسا", "چکاوک", "ژاله", "کاوه", "گلناز", "یاسمن"] alphabet: ["آرش", "بابک", "پریسا", "چکاوک", "حسن", "زهرا", "ژاله", "کاوه", "گلناز", "وحید", "هما", "یاسمن"]

The 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.

JobUse
Numbers or strings, ascendingSort, or Sorted for a copy
DescendingSortDesc
Structs or your own orderSortBy, SortedBy
Keep ties in order, or few distinct keysStableSortBy
Keep parallel vectors togetherSortIndex, SortIndexDesc
Find in a sorted vectorBinarySearch, LowerBound, UpperBound
Check an orderIsSorted, IsSortedBy

Functions

Swap

func Swap<T>(v: Vector<T>, i: int, j: int)
Exchanges two elements of a vector.
sort-Sort.salam
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
end
Outputfalse [1, 3, 5, 7, 9] [5, 3, 9, 1, 7] [1, 3, 5, 7, 9] true [9, 7, 5, 3, 1] [1, 3, 5, 7, 9] 1 9 [9, 3, 5, 7, 1]

SortBy

func SortBy<T>(v: Vector<T>, less: func(T, T): bool)
Sorts the vector with the comparison function 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.
sort-SortBy.salam
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
end
OutputMaryam Sara Reza Ali true Ali Ali

StableSortBy

func StableSortBy<T>(v: Vector<T>, less: func(T, T): bool)
Like 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>
A sorted copy, using your own comparison (with 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): bool
True when the vector is sorted according to the comparison function.

The example for this item is shown with the ones above: sort-SortBy.salam

BucketSort

func BucketSort(v: Vector<int>)
Bucket sort for whole numbers; fast when the numbers are spread evenly over a range.
sort-IntSorts.salam
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
end
Output[2, 24, 45, 66, 75, 90, 170, 802] [2, 24, 45, 66, 75, 90, 170, 802] [2, 24, 45, 66, 75, 90, 170, 802]

CountingSort

func CountingSort(v: Vector<int>)
Counting sort for whole numbers; very fast when the range of values is small. It allocates one counter for every value between the smallest and the largest, so a wide range uses a lot of memory.

The example for this item is shown with the ones above: sort-IntSorts.salam

RadixSort

func RadixSort(v: Vector<int>)
Radix sort for whole numbers; it sorts digit by digit and makes no comparisons.

The example for this item is shown with the ones above: sort-IntSorts.salam

PancakeSort

func PancakeSort<T>(v: Vector<T>)
Pancake sort, which sorts using nothing but reversals of a prefix. For teaching.
sort-Algorithms.salam
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
end
Outputtrue true true true true true true true true true true true true [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

CombSort

func CombSort<T>(v: Vector<T>)
Comb sort, an improved bubble sort.

The example for this item is shown with the ones above: sort-Algorithms.salam

BubbleSort

func BubbleSort<T>(v: Vector<T>)
Bubble sort: simple and slow, for teaching.

The example for this item is shown with the ones above: sort-Algorithms.salam

BinarySearch

func BinarySearch<T>(v: Vector<T>, x: T): int
Finds x 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.
sort-BinarySearch.salam
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)
end
Output4 -1 1 4

LowerBound

func LowerBound<T>(v: Vector<T>, x: T): int
The first position whose element is not less than x: 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): int
The first position whose element is greater than x. 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>)
Instead of sorting the data, sorts the indices in 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.
sort-SortIndex.salam
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 ""
end
OutputShiraz Tabriz Tehran Tehran Tabriz Shiraz

SortIndexDesc

func SortIndexDesc(idx &: Vector<int>, keys &: Vector<f64>)
Like 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>)
Odd-even sort, designed for parallel processing.

The example for this item is shown with the ones above: sort-Algorithms.salam

GnomeSort

func GnomeSort<T>(v: Vector<T>)
Gnome sort: like insertion sort, simple and slow.

The example for this item is shown with the ones above: sort-Algorithms.salam

SelectionSort

func SelectionSort<T>(v: Vector<T>)
Selection sort, which brings the smallest remaining element forward each time.

The example for this item is shown with the ones above: sort-Algorithms.salam

HeapSort

func HeapSort<T>(v: Vector<T>)
Heap sort: always fast, n log n, and needs no extra memory.

The example for this item is shown with the ones above: sort-Algorithms.salam

MergeSort

func MergeSort<T>(v: Vector<T>)
Merge sort: always fast and stable, but it needs extra memory.

The example for this item is shown with the ones above: sort-Algorithms.salam

ShellSort

func ShellSort<T>(v: Vector<T>)
Shell sort, a faster insertion sort.

The example for this item is shown with the ones above: sort-Algorithms.salam

InsertionSort

func InsertionSort<T>(v: Vector<T>)
Insertion sort, very good on small or nearly sorted vectors.

The example for this item is shown with the ones above: sort-Algorithms.salam

BinaryInsertionSort

func BinaryInsertionSort<T>(v: Vector<T>)
An insertion sort that finds the insertion point by binary search.

The example for this item is shown with the ones above: sort-Algorithms.salam

IntroSort

func IntroSort<T>(v: Vector<T>)
Introsort: it starts as a quick sort and switches to a heap sort when it has to, so it never degrades.

The example for this item is shown with the ones above: sort-Algorithms.salam

IsSorted

func IsSorted<T>(v: Vector<T>): bool
True when the vector is sorted in ascending order.

The example for this item is shown with the ones above: sort-Sort.salam

Reverse

func Reverse<T>(v: Vector<T>)
Reverses the order of the vector's elements.

The example for this item is shown with the ones above: sort-Sort.salam

Min

func Min<T>(v: Vector<T>): T
The smallest element of the vector. The vector must not be empty.

The example for this item is shown with the ones above: sort-Sort.salam

Max

func Max<T>(v: Vector<T>): T
The largest element of the vector. The vector must not be empty.

The example for this item is shown with the ones above: sort-Sort.salam

Sort

func Sort<T>(v: Vector<T>)
Sorts the vector in ascending order with an introsort: n log n on any input, not stable. The default choice for sorting. Strings are compared byte by byte.

The example for this item is shown with the ones above: sort-Sort.salam

SortDesc

func SortDesc<T>(v: Vector<T>)
Sorts the vector in descending order: an ascending sort followed by a reverse.

The example for this item is shown with the ones above: sort-Sort.salam

Sorted

func Sorted<T>(v: Vector<T>): Vector<T>
An ascending sorted copy of the vector; the original is unchanged.

The example for this item is shown with the ones above: sort-Sort.salam

QuickSort

func QuickSort<T>(v: Vector<T>)
Quick sort, the fastest in practice for random data; it can become slow on many equal values.

The example for this item is shown with the ones above: sort-Algorithms.salam

CocktailSort

func CocktailSort<T>(v: Vector<T>)
Cocktail sort, a bubble sort that runs left to right and back again on each pass.

The example for this item is shown with the ones above: sort-Algorithms.salam