zermelo

README

zermelo v2

A radix sorting library for Go. Trade memory for speed! Now with more generics!

import "github.com/shawnsmithdev/zermelo/v2"

func foo(large []uint64)
    zermelo.Sort(large)
}

About

Zermelo is a sorting library featuring implementations of radix sort. I am especially influenced here by these two articles that describe various optimizations and how to work around the typical limitations of radix sort.

You will generally only want to use zermelo if you won't mind the extra memory used for buffers and your application frequently sorts slices of supported types with at least 256 elements (128 for 32-bit types, 386 for []float64). The larger the slices you are sorting, the more benefit you will gain by using zermelo instead of the standard library's in-place comparison sort slices.Sort().

Etymology

Zermelo is named after Ernst Zermelo, who developed the proof for the well-ordering theorem.

Supported Types

Sort and NewSorter support integer slices, that is []int, []uint64, []byte, etc, and derived types.

Sorter

A Sorter returned by NewSorter will reuse buffers created during Sort() calls. This is not thread safe. Buffers are grown as needed at a 25% exponential growth rate. This means if you sort a slice of size n, subsequent calls with slices up to n * 1.25 in length will not cause another buffer allocation. This does not apply to the first allocation, which will make a buffer of the same size as the requested slice. This way, if the slices being sorted do not grow in size, there is no unused buffer space.

import "github.com/shawnsmithdev/zermelo/v2"

func foo(bar [][]uint64) {
    sorter := zermelo.NewSorter[uint64]()
    for _, x := range bar {
        sorter.Sort(x)
    }
}

Float Subpackage

SortFloats and FloatSorter provided in the floats subpackage support float slices, specifically []float32 and []float64 and derived types. This uses the unsafe package to treat floats as though they were unsigned integers.

import "github.com/shawnsmithdev/zermelo/v2/floats"

func foo(bar [][]floats64) {
    sorter := floats.NewFloatSorter[float64]()
    for _, x := range bar {
        sorter.Sort(x)
    }
}

Documentation

Overview

Package zermelo is a library for sorting slices in Go.

Index

• func Sort[T Integer](x []T)
• func SortBYOB[T Integer](x, buffer []T)
• type Integer
• type Signed
• type Sorter
  • func NewSorter[I Integer]() Sorter[I]
• type Unsigned

Functions

func Sort

func Sort[T Integer](x []T)

Sort sorts integer slices. If the slice is large enough, radix sort is used by allocating a new buffer.

func SortBYOB

func SortBYOB[T Integer](x, buffer []T)

SortBYOB sorts integer slices with radix sort using the provided buffer. len(buffer) must be greater or equal to len(x).

Types

type Integer

type Integer interface {
	Signed | Unsigned
}

Integer is a constraint that permits any integer type.

type Signed

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

Signed is a constraint that permits any signed integer type.

type Sorter

type Sorter[T cmp.Ordered] interface {
	// Sort sorts slices in ascending order.
	Sort(x []T)
}

Sorter describes types that can sort slices.

func NewSorter

func NewSorter[I Integer]() Sorter[I]

NewSorter creates a new Sorter that will use radix sort on large slices and reuses buffers. The first sort creates a buffer the same size as the slice being sorted and keeps it for future use. Later sorts may grow this buffer as needed. The Sorter returned is not thread safe. Using this sorter can be much faster than repeat calls to Sort.

type Unsigned

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

Unsigned is a constraint that permits any unsigned integer type.