sort!(
    v::AbstractArray;
    backend=nothing,
    alg::Algorithm=Auto(),
    dims::Union{Colon, Integer}=:,
    lt=isless, by=identity, rev::Union{Nothing, Bool}=nothing,
    order::Base.Order.Ordering=Base.Order.Forward,
    workspace=nothing,
) -> v

Sort v in place. lt, by, rev and order are those of Base.sort!, and so is the result: by default the sort is stable. dims=: sorts the whole array as one vector (Base.sort! requires dims for arrays of more than one dimension); an integer dims sorts each slice along that dimension independently.

alg is Auto() by default, which chooses an algorithm for the backend and device, the element type, the ordering, and the length of the array or slices: on the host, CPUThreads.SampleSort; on GPUs, BitonicSort for short arrays and slices, RadixSort for long ones of the element types and orderings it supports, and MergeSort otherwise, with lengths measured for each backend (MergeSort on backends without such measurements). BitonicSort is unstable, so by default Auto uses it only where equal elements are identical (integers, Bool, Char under the default ordering or its reverse); Auto(stable=false) also allows it for others (e.g. floats). An explicit algorithm, with any of its settings, is used as given or rejected with an ArgumentError.

backend is derived from v; pass it only for arrays that do not determine their backend.

workspace takes the scratch memory of a workspace made for the same call, so that the sort allocates none of its own.

Examples

import AcceleratedKernels as AKusing CUDAv = CuArray(rand(Float32, 100_000))AK.sort!(v)                                         # Auto: stable, chosen for the deviceAK.sort!(v; rev=true, alg=AK.Auto(stable=false))    # may use an unstable algorithmAK.sort!(v; alg=AK.RadixSort(block_size=512))       # this algorithm, with this settingA = CuArray(rand(Int32, 64, 10_000))AK.sort!(A; dims=1)                                 # each columnAK.sort!(rand(1000))                                # host array: Julia threads

sort(v::AbstractArray; kwargs...)

Out-of-place sort!: sort a copy of v, with the same keywords.

sortperm!(
    ix::AbstractArray,
    v::AbstractArray;
    backend=nothing,
    alg::Algorithm=Auto(),
    dims::Union{Colon, Integer}=:,
    lt=isless, by=identity, rev::Union{Nothing, Bool}=nothing,
    order::Base.Order.Ordering=Base.Order.Forward,
    workspace=nothing,
) -> ix

Write into ix the stable permutation that sorts v, so that v[ix] is sorted; ix is always overwritten. The keywords are those of sort!.

With dims=:, ix needs as many elements as v and receives v's linear indices (1:length(v), unless v is a vector whose axis starts elsewhere). With an integer dims, ix must have the same axes as v and receives linear indices into v, so that v[ix] is sorted along dims, like Base.sortperm!(ix, A; dims).

Auto() chooses CPUThreads.SampleSort on the host and MergeSort on GPUs; MergeSort(lowmem=true) avoids copying the keys. RadixSort and BitonicSort have no permutation path. backend is derived from ix and v.

sortperm(v::AbstractArray; kwargs...)

Out-of-place sortperm!: return an Int array of v's size, with axes starting at 1, holding the permutation, with the same keywords.

sort_by_key!(
    keys::AbstractArray,
    values::AbstractArray;
    backend=nothing,
    alg::Algorithm=Auto(),
    dims::Union{Colon, Integer}=:,
    lt=isless, by=identity, rev::Union{Nothing, Bool}=nothing,
    order::Base.Order.Ordering=Base.Order.Forward,
    workspace=nothing,
) -> (keys, values)

Sort keys in place and apply the same permutation to values, stably: values with equal keys keep their relative order. The ordering keywords and dims are those of sort!; values must have as many elements as keys (the same axes with an integer dims).

Auto() chooses CPUThreads.SampleSort on the host and MergeSort on GPUs, the algorithms that support key/value sorting. backend is derived from keys and values.

Thrust, oneDPL and Kokkos call this operation sort_by_key, CUB SortPairs.

Examples

import AcceleratedKernels as AKusing Metalkeys = MtlArray(rand(Int32(1):Int32(10), 1000))values = MtlArray(Int32.(1:1000))AK.sort_by_key!(keys, values)      # values of equal keys stay in ascending order

SortAlgorithm <: Algorithm

Supertype of the sorting algorithms: MergeSort, RadixSort, BitonicSort and CPUThreads.SampleSort.

MergeSort(; block_size=nothing, lowmem=false)

GPU merge sort: stable, for every element type and ordering, whole arrays and dims, and the only kernel algorithm for sortperm! and sort_by_key!. Each block of block_size threads (a power of two) sorts a tile of 2 * block_size elements in local memory, then global passes merge the tiles. A tile, with the values moved along, must fit in 32 KiB; for large elements, the default block_size shrinks to fit. lowmem=true selects a sortperm! path that does not copy the keys, at the cost of reading them from global memory in every comparison; other operations reject it.

RadixSort(; block_size=nothing, items_per_thread=nothing, chunk_size=nothing)

GPU LSD radix sort: stable, for UInt32, Int32, Float32, UInt64, Int64 and Float64 under the default ordering or its reverse (floats ordered like isless), on whole arrays and along dims, with at most 2^32 elements per array or slice. It supports neither custom lt/by nor sortperm! or sort_by_key!.

block_size is a power of two up to 1024. Where the backend has atomics, chunk_size (a power of two up to 1024) divides block_size and the tile fits local memory, each thread sorts items_per_thread (1 to 64) elements, ranking each among the earlier elements of its chunk: chunk_size trades those comparisons against the chunks' histograms in local memory. Elsewhere each thread sorts one element.

Along dims, each pass sorts all slices at once. It pays off for long slices: every slice takes at least one block of the passes, so short ones leave most threads idle, and slices along other dimensions than the first are read with a stride. Where each thread sorts items_per_thread elements and a slice of up to 2 * block_size elements fits in local memory, one block sorts each slice there instead.

BitonicSort(; block_size=nothing, items_per_thread=nothing)

GPU bitonic sorting network, for whole arrays and dims, every element type and ordering. It is unstable and does not support sortperm! or sort_by_key!. Fastest for small arrays and short slices: tiles of block_size * items_per_thread elements sort in local memory, larger inputs need global passes. Both settings must be positive powers of two, and a tile must fit in 32 KiB.

CPUThreads.SampleSort(; max_tasks=nothing, min_elems=nothing)

Parallel sample sort on Julia threads, deferring to Base.sort! for the local sorts; it is stable, and also provides sortperm! and sort_by_key!. Uses at most max_tasks tasks (default Threads.nthreads()), each with at least min_elems elements (default 1). Only runs on the host backend.