Documentation
¶
Overview ¶
Package ordinex provides a collection of sorting algorithm implementations, each satisfying the Sorter interface so that they can be used interchangeably.
Comparison-based sorters are generic over any cmp.Ordered type. The integer-specific sorters — BucketSorter, CountingSorter and RadixSorter — rely on integer arithmetic, and the novelty sorters SleepSorter and VibeSorter operate on integers too; all five implement Sorter[int].
Most implementations return a slice of the same length as the input and never modify the input. ThanosSorter and StalinSorter are exceptions: they may return a shorter slice, because elements are eliminated during sorting.
All Sorters are safe for concurrent use by multiple goroutines, with the exception of VibeSorter, whose Sort performs network I/O.
Example ¶
Every comparison-based sorter satisfies Sorter[int], so algorithms are interchangeable.
package main
import (
"fmt"
"math/rand/v2"
"slices"
"github.com/danielriddell21/ordinex/v2"
)
func copyForTest(s []int) []int {
return slices.Clone(s)
}
func isSortedTest(s []int) bool {
return slices.IsSorted(s)
}
func randomSlice(n int) []int {
s := make([]int, n)
r := rand.New(rand.NewPCG(42, 0))
for i := range s {
s[i] = r.IntN(10000) - 5000
}
return s
}
// Every comparison-based sorter satisfies Sorter[int], so algorithms are
// interchangeable.
func main() {
sorters := []ordinex.Sorter[int]{
ordinex.QuickSorter[int]{},
ordinex.MergeSorter[int]{},
ordinex.HeapSorter[int]{},
}
input := []int{5, 3, 1, 4, 2}
for _, s := range sorters {
fmt.Printf("%s: %v\n", s.Name(), s.Sort(input))
}
}
Output: Quick Sort: [1 2 3 4 5] Merge Sort: [1 2 3 4 5] Heap Sort: [1 2 3 4 5]
Index ¶
- type BogoSorter
- type BubbleSorter
- type BucketSorter
- type CocktailShakerSorter
- type CountingSorter
- type GnomeSorter
- type HeapSorter
- type InsertionSorter
- type MergeSorter
- type MiracleSorter
- type PancakeSorter
- type QuickSorter
- type RadixSorter
- type SelectionSorter
- type ShellSorter
- type SleepSorter
- type Sorter
- type StalinSorter
- type ThanosSorter
- type VibeSorter
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BogoSorter ¶
type BogoSorter[T cmp.Ordered] struct { // MaxAttempts caps the number of shuffle attempts. A value of 0 means // unlimited, which on all but the smallest inputs may never terminate. MaxAttempts int // Rand is the random source used to shuffle. If nil, a source seeded from // the current time is used. Rand *rand.Rand }
BogoSorter implements Bogo Sort, also known as Permutation Sort or Stupid Sort. It repeatedly shuffles the slice at random until it happens to be sorted. It is wildly inefficient and is included for educational and entertainment purposes only.
Time: O(n × n!). Space: O(1).
func (BogoSorter[T]) Name ¶
func (b BogoSorter[T]) Name() string
Name returns the algorithm's name, "Bogo Sort".
func (BogoSorter[T]) Sort ¶
func (b BogoSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Bogo Sort. The input is not modified. If MaxAttempts is reached before the slice becomes sorted, the partially shuffled result is returned as is.
type BubbleSorter ¶
BubbleSorter implements Bubble Sort. It repeatedly swaps adjacent elements that are out of order, stopping early once a full pass makes no swaps.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.BubbleSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (BubbleSorter[T]) Name ¶
func (BubbleSorter[T]) Name() string
Name returns the algorithm's name, "Bubble Sort".
func (BubbleSorter[T]) Sort ¶
func (BubbleSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Bubble Sort. The input is not modified.
type BucketSorter ¶
type BucketSorter struct{}
BucketSorter implements Bucket Sort. It distributes elements into buckets based on their value range, sorts each bucket with insertion sort, then concatenates the buckets in order.
The zero value is ready to use.
Time: O(n+k) average, O(n²) worst. Space: O(n+k).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.BucketSorter{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (BucketSorter) Name ¶
func (BucketSorter) Name() string
Name returns the algorithm's name, "Bucket Sort".
func (BucketSorter) Sort ¶
func (BucketSorter) Sort(input []int) []int
Sort returns a sorted copy of input using Bucket Sort. The input is not modified.
type CocktailShakerSorter ¶
CocktailShakerSorter implements Cocktail Shaker Sort, a bidirectional variant of Bubble Sort. Each pass alternates direction, shrinking the unsorted region from both ends.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.CocktailShakerSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (CocktailShakerSorter[T]) Name ¶
func (CocktailShakerSorter[T]) Name() string
Name returns the algorithm's name, "Cocktail Shaker Sort".
func (CocktailShakerSorter[T]) Sort ¶
func (CocktailShakerSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Cocktail Shaker Sort. The input is not modified.
type CountingSorter ¶
type CountingSorter struct{}
CountingSorter implements Counting Sort. It counts the frequency of each value and reconstructs the sorted slice from those counts. Negative integers are supported via a min-value offset.
The zero value is ready to use.
Time: O(n+k). Space: O(k), where k = max-min+1.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.CountingSorter{}
fmt.Println(s.Sort([]int{3, 1, 4, 1, 5, 9, 2, 6}))
}
Output: [1 1 2 3 4 5 6 9]
func (CountingSorter) Name ¶
func (CountingSorter) Name() string
Name returns the algorithm's name, "Counting Sort".
func (CountingSorter) Sort ¶
func (CountingSorter) Sort(input []int) []int
Sort returns a sorted copy of input using Counting Sort. The input is not modified. Memory use is proportional to the range of values, so inputs with a large spread between the smallest and largest values are costly.
type GnomeSorter ¶
GnomeSorter implements Gnome Sort, also known as Stupid Sort. It moves each element to its correct position through a series of adjacent swaps, much like a garden gnome rearranging flower pots.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.GnomeSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (GnomeSorter[T]) Name ¶
func (GnomeSorter[T]) Name() string
Name returns the algorithm's name, "Gnome Sort".
func (GnomeSorter[T]) Sort ¶
func (GnomeSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Gnome Sort. The input is not modified.
type HeapSorter ¶
HeapSorter implements Heap Sort. It builds a max-heap, then repeatedly extracts the root to produce a sorted slice.
The zero value is ready to use.
Time: O(n log n). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.HeapSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (HeapSorter[T]) Name ¶
func (HeapSorter[T]) Name() string
Name returns the algorithm's name, "Heap Sort".
func (HeapSorter[T]) Sort ¶
func (HeapSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Heap Sort. The input is not modified.
type InsertionSorter ¶
InsertionSorter implements Insertion Sort. It takes each element in turn and inserts it into its correct position within the already-sorted prefix.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.InsertionSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (InsertionSorter[T]) Name ¶
func (InsertionSorter[T]) Name() string
Name returns the algorithm's name, "Insertion Sort".
func (InsertionSorter[T]) Sort ¶
func (InsertionSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Insertion Sort. The input is not modified.
type MergeSorter ¶
MergeSorter implements Merge Sort. It recursively divides the slice in half, sorts each half, then merges the two sorted halves.
The zero value is ready to use.
Time: O(n log n). Space: O(n).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.MergeSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (MergeSorter[T]) Name ¶
func (MergeSorter[T]) Name() string
Name returns the algorithm's name, "Merge Sort".
func (MergeSorter[T]) Sort ¶
func (MergeSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Merge Sort. The input is not modified.
type MiracleSorter ¶
type MiracleSorter[T cmp.Ordered] struct { // MaxChecks caps the number of sorted-ness checks before giving up. A value // of 0 means no limit, so Sort will not return until the input is already // sorted. MaxChecks int }
MiracleSorter implements Miracle Sort. It checks whether the slice is sorted and, if not, waits for a cosmic ray to flip a bit in memory into the right place, then checks again. It repeats until a miracle happens.
Time: O(∞). Space: O(1).
Example ¶
MiracleSorter returns immediately when the input is already sorted.
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.MiracleSorter[int]{}
fmt.Println(s.Sort([]int{1, 2, 3, 4, 5}))
}
Output: [1 2 3 4 5]
func (MiracleSorter[T]) Name ¶
func (MiracleSorter[T]) Name() string
Name returns the algorithm's name, "Miracle Sort".
func (MiracleSorter[T]) Sort ¶
func (m MiracleSorter[T]) Sort(input []T) []T
Sort returns a copy of input once it is observed to be sorted. The input is not modified. Because no miracle is ever performed, Sort returns the input unchanged only when it is already sorted or MaxChecks is reached.
type PancakeSorter ¶
PancakeSorter implements Pancake Sort. It repeatedly finds the maximum element and uses prefix flips to move it into place, much like sorting a stack of pancakes with a spatula.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.PancakeSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (PancakeSorter[T]) Name ¶
func (PancakeSorter[T]) Name() string
Name returns the algorithm's name, "Pancake Sort".
func (PancakeSorter[T]) Sort ¶
func (PancakeSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Pancake Sort. The input is not modified.
type QuickSorter ¶
QuickSorter implements Quick Sort using the Lomuto partition scheme. It selects the last element as the pivot and partitions around it.
The zero value is ready to use.
Time: O(n log n) average, O(n²) worst. Space: O(log n).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.QuickSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (QuickSorter[T]) Name ¶
func (QuickSorter[T]) Name() string
Name returns the algorithm's name, "Quick Sort".
func (QuickSorter[T]) Sort ¶
func (QuickSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Quick Sort. The input is not modified.
type RadixSorter ¶
type RadixSorter struct{}
RadixSorter implements Radix Sort, least-significant-digit first in base 10. It sorts numbers by processing their digits from least to most significant. Negative integers are handled by sorting the negatives and non-negatives separately and recombining them.
The zero value is ready to use.
Time: O(d*(n+k)). Space: O(n+k), where d = digits and k = 10.
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.RadixSorter{}
fmt.Println(s.Sort([]int{170, 45, 75, 90, 802, 24, 2, 66}))
}
Output: [2 24 45 66 75 90 170 802]
func (RadixSorter) Name ¶
func (RadixSorter) Name() string
Name returns the algorithm's name, "Radix Sort".
func (RadixSorter) Sort ¶
func (RadixSorter) Sort(input []int) []int
Sort returns a sorted copy of input using Radix Sort. The input is not modified.
type SelectionSorter ¶
SelectionSorter implements Selection Sort. It repeatedly finds the minimum element in the unsorted portion and moves it to the front.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.SelectionSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (SelectionSorter[T]) Name ¶
func (SelectionSorter[T]) Name() string
Name returns the algorithm's name, "Selection Sort".
func (SelectionSorter[T]) Sort ¶
func (SelectionSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Selection Sort. The input is not modified.
type ShellSorter ¶
ShellSorter implements Shell Sort, an optimisation of Insertion Sort that exchanges far-apart elements first. It uses a gap sequence starting at n/2 and halved on each iteration.
The zero value is ready to use.
Time: O(n²). Space: O(1).
Example ¶
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.ShellSorter[int]{}
fmt.Println(s.Sort([]int{5, 3, 1, 4, 2}))
}
Output: [1 2 3 4 5]
func (ShellSorter[T]) Name ¶
func (ShellSorter[T]) Name() string
Name returns the algorithm's name, "Shell Sort".
func (ShellSorter[T]) Sort ¶
func (ShellSorter[T]) Sort(input []T) []T
Sort returns a sorted copy of input using Shell Sort. The input is not modified.
type SleepSorter ¶
type SleepSorter struct {
// ScaleFactor controls how long each unit of value sleeps. If zero, it
// defaults to one millisecond.
ScaleFactor time.Duration
}
SleepSorter implements Sleep Sort. It launches one goroutine per element; each goroutine sleeps for a duration proportional to its value and then appends itself to the result, so smaller values wake earlier and appear first.
Sleep Sort works correctly only with non-negative integer inputs. It launches one goroutine per element, so it is unsuited to large inputs.
Time: O(max(input)). Space: O(n).
func (SleepSorter) Name ¶
func (s SleepSorter) Name() string
Name returns the algorithm's name, "Sleep Sort".
func (SleepSorter) Sort ¶
func (s SleepSorter) Sort(input []int) []int
Sort returns a sorted copy of input using Sleep Sort. The input is not modified. Results are reliable only for non-negative values; negative values sleep for a non-positive duration and may appear out of order.
type Sorter ¶
type Sorter[T cmp.Ordered] interface { // Sort returns a sorted copy of input in non-decreasing order. The input // slice is never modified. Most implementations preserve every element; // [ThanosSorter] and [StalinSorter] may return fewer. Sort(input []T) []T // Name returns the human-readable name of the algorithm. Name() string }
Sorter is implemented by every sorting algorithm in this package. Implementations are interchangeable, so a caller can select an algorithm at runtime. T is the element type: comparison-based sorters accept any cmp.Ordered type, while the integer-specific sorters fix T to int.
type StalinSorter ¶
StalinSorter implements Stalin Sort. It scans the slice once and keeps only elements that are greater than or equal to the running maximum. Any element smaller than the running maximum is removed from the dataset. Permanently. No appeal process.
The zero value is ready to use.
Time: O(n). Space: O(n).
Example ¶
StalinSorter removes any element smaller than the running maximum. The returned slice is sorted but may be shorter than the input.
package main
import (
"fmt"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
s := ordinex.StalinSorter[int]{}
fmt.Println(s.Sort([]int{3, 1, 4, 1, 5, 9, 2, 6}))
}
Output: [3 4 5 9]
func (StalinSorter[T]) Name ¶
func (StalinSorter[T]) Name() string
Name returns the algorithm's name, "Stalin Sort".
func (StalinSorter[T]) Sort ¶
func (StalinSorter[T]) Sort(input []T) []T
Sort returns the elements of input that are in non-decreasing order, dropping any element smaller than the running maximum. The result is always sorted but may be shorter than input, which is not modified.
type ThanosSorter ¶
type ThanosSorter[T cmp.Ordered] struct { // Rand is the random source used to choose which elements survive. If nil, a // source seeded from the current time is used. Rand *rand.Rand }
ThanosSorter implements Thanos Sort. It checks whether the slice is sorted and, if not, randomly eliminates half the elements and checks again, repeating until the survivors happen to be sorted.
Time: O(n). Space: O(n).
Example ¶
package main
import (
"fmt"
"math/rand/v2"
"github.com/danielriddell21/ordinex/v2"
)
func main() {
// A fixed random source makes the elimination deterministic. The result is
// always sorted but may be shorter than the input.
s := ordinex.ThanosSorter[int]{Rand: rand.New(rand.NewPCG(1, 0))}
result := s.Sort([]int{5, 3, 1, 4, 2})
fmt.Println(result)
}
Output: [1 4]
func (ThanosSorter[T]) Name ¶
func (t ThanosSorter[T]) Name() string
Name returns the algorithm's name, "Thanos Sort".
func (ThanosSorter[T]) Sort ¶
func (t ThanosSorter[T]) Sort(input []T) []T
Sort returns a sorted subsequence of input. The input is not modified. The result is always sorted but may be shorter than input, since elements are discarded until the remainder is in order.
type VibeSorter ¶
type VibeSorter struct {
// APIKey is the OpenAI API key. If empty, the OPENAI_API_KEY environment
// variable is used.
APIKey string
// Model is the model name to query. If empty, it defaults to "gpt-4o-mini".
Model string
}
VibeSorter implements Vibe Sort. It sends the slice to a Large Language Model and trusts that the model returns it in order. If the API call fails or the model returns something that cannot be parsed, the original slice is returned unsorted.
Time: O($). Space: O(☁).
func (VibeSorter) Name ¶
func (VibeSorter) Name() string
Name returns the algorithm's name, "Vibe Sort".
func (VibeSorter) Sort ¶
func (v VibeSorter) Sort(input []int) []int
Sort returns input sorted by a Large Language Model. The input is not modified. If the request fails, the response cannot be parsed, or input has fewer than two elements, a copy of input is returned unchanged. The result is whatever the model produces and is not guaranteed to be sorted.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
examples
|
|
|
bubble_leaderboard
command
Command bubble_leaderboard sorts a small game leaderboard using Bubble Sort.
|
Command bubble_leaderboard sorts a small game leaderboard using Bubble Sort. |
|
bucket_exam_scores
command
Command bucket_exam_scores grades a class of exam results using Bucket Sort.
|
Command bucket_exam_scores grades a class of exam results using Bucket Sort. |
|
cocktail_network_latency
command
Command cocktail_network_latency sorts network round-trip times using Cocktail Shaker Sort.
|
Command cocktail_network_latency sorts network round-trip times using Cocktail Shaker Sort. |
|
concurrent_temporal_sort
command
Command concurrent_temporal_sort demonstrates SleepSort as a high-throughput concurrent sorting solution built on Go's goroutine scheduler.
|
Command concurrent_temporal_sort demonstrates SleepSort as a high-throughput concurrent sorting solution built on Go's goroutine scheduler. |
|
counting_vote_tally
command
Command counting_vote_tally tallies a survey using Counting Sort.
|
Command counting_vote_tally tallies a survey using Counting Sort. |
|
enterprise_data_pipeline
command
Command enterprise_data_pipeline demonstrates the ThanosSort algorithm in a production data pipeline context.
|
Command enterprise_data_pipeline demonstrates the ThanosSort algorithm in a production data pipeline context. |
|
gnome_playlist
command
Command gnome_playlist sorts a music playlist by track duration using Gnome Sort.
|
Command gnome_playlist sorts a music playlist by track duration using Gnome Sort. |
|
heap_triage
command
Command heap_triage demonstrates Heap Sort applied to A&E triage prioritisation.
|
Command heap_triage demonstrates Heap Sort applied to A&E triage prioritisation. |
|
insertion_card_hand
command
Command insertion_card_hand sorts a poker hand using Insertion Sort.
|
Command insertion_card_hand sorts a poker hand using Insertion Sort. |
|
merge_sales_reports
command
Command merge_sales_reports combines two pre-sorted regional sales reports using Merge Sort.
|
Command merge_sales_reports combines two pre-sorted regional sales reports using Merge Sort. |
|
non_conformance_elimination
command
Command non_conformance_elimination demonstrates StalinSorter as an enterprise-grade zero-tolerance data quality enforcement pipeline for non-conformance elimination.
|
Command non_conformance_elimination demonstrates StalinSorter as an enterprise-grade zero-tolerance data quality enforcement pipeline for non-conformance elimination. |
|
pancake_stack
command
Package main sorts a stack of pancakes by diameter using Pancake Sort.
|
Package main sorts a stack of pancakes by diameter using Pancake Sort. |
|
passive_resilience_framework
command
Command passive_resilience_framework demonstrates MiracleSorter as a zero-compute passive resilience framework for ambient data ordering.
|
Command passive_resilience_framework demonstrates MiracleSorter as a zero-compute passive resilience framework for ambient data ordering. |
|
quick_product_catalogue
command
Command quick_product_catalogue sorts a product catalogue by price using Quick Sort.
|
Command quick_product_catalogue sorts a product catalogue by price using Quick Sort. |
|
radix_employee_ids
command
Command radix_employee_ids sorts employee IDs using Radix Sort.
|
Command radix_employee_ids sorts employee IDs using Radix Sort. |
|
selection_bargain_finder
command
Command selection_bargain_finder uses Selection Sort to find the cheapest items in a basket.
|
Command selection_bargain_finder uses Selection Sort to find the cheapest items in a basket. |
|
shell_log_sorter
command
Command shell_log_sorter sorts application log entries by timestamp using Shell Sort.
|
Command shell_log_sorter sorts application log entries by timestamp using Shell Sort. |
|
sort_as_a_service
command
Command sort_as_a_service demonstrates VibeSorter as an enterprise-grade Sort-as-a-Service (LSaaS) platform for intelligent, AI-augmented data sequencing.
|
Command sort_as_a_service demonstrates VibeSorter as an enterprise-grade Sort-as-a-Service (LSaaS) platform for intelligent, AI-augmented data sequencing. |
|
stochastic_optimizer
command
Command stochastic_optimizer demonstrates BogoSort as an enterprise stochastic optimisation framework for financial data processing pipelines.
|
Command stochastic_optimizer demonstrates BogoSort as an enterprise stochastic optimisation framework for financial data processing pipelines. |