Sort StaticVector?

Hi,

I wonder if there is specific sorting functions for StaticArrays (e.g. sorting network) ?

I found this GitHub - JeffreySarnoff/SortingNetworks.jl: Sort 1..25 values with conditional swaps !
Unfortunately, it stops at 25 item (I have 40…)

StaticArrays have the advantage of compile-time known size. Other than for small sizes (less than 20), I think this does not help substantially for sorting. So going with regular sorting routines should not add significant overhead.

As for sorting networks (which are in a different model of computation than CPUs which are Von Neumann / Turing type), they can be easily recursively defined for larger arrays, but since they are not adaptive to data, they are actually worse in the sense of doing some spurious comparisons (e.g. if a < b and b < c, we do not need to compute a < c, but this cannot be known before the first two comparisons are made).

1 Like

StaticArrays uses BitonicSort for static arrays of length less than 20. For longer arrays it might not be useful but it is possible although not documented:

x = @SArray(rand(40))
sort(x, alg=StaticArrays.BitonicSort)
1 Like

This has been requested before. I will add implementations through 32 inputs
.

1 Like

ahh – you want to do this with 40 items – so I will extend it to 48 items.

3 Likes

here is swapsort for 40 items (exactly)
each empty line separates the 17 internally parallelizable layers
each group must be processed in order (sequentially)
there are 265 comparisons

faster than sort
with
3x Float32
2x Float64
1.5x Int
const ITEMS_MAX = 40
const VALS = ([Val{i} for i=1:ITEMS_MAX]...,)

@inline function min_max(a::T, b::T) where {T<:Real}
     return (b < a ? (b, a) : (a, b))
end

@inline function swapsort(vec::AbstractVector{T}) where {T}
    n = length(vec)
    n > ITEMS_MAX && throw(ErrorException("swapsort(vector) not defined where length(vector) > $ITEMS_MAX"))
    return swapsort(VALS[length(vec)], vec)
end

function swapsort(a::T, b::T, c::T, d::T, e::T, f::T, g::T, h::T, i::T, j::T, k::T, l::T, m::T, n::T, o::T, p::T, q::T, r::T, s::T, t::T, u::T, v::T, w::T, x::T, y::T, z::T, aa::T, bb::T, cc::T, dd::T, ee::T, ff::T, gg::T, hh::T, ii::T, jj::T, kk::T, ll::T, mm::T, nn::T) where {T}

    a, b = min_max(a, b)
    c, d = min_max(c, d)
    e, f = min_max(e, f)
    g, h = min_max(g, h)
    i, j = min_max(i, j)
    k, l = min_max(k, l)
    m, n = min_max(m, n)
    o, p = min_max(o, p)
    q, r = min_max(q, r)
    s, t = min_max(s, t)
    u, v = min_max(u, v)
    w, x = min_max(w, x)
    y, z = min_max(y, z)
    aa, bb = min_max(aa, bb)
    cc, dd = min_max(cc, dd)
    ee, ff = min_max(ee, ff)
    gg, hh = min_max(gg, hh)
    ii, jj = min_max(ii, jj)
    kk, ll = min_max(kk, ll)
    mm, nn = min_max(mm, nn)

    a, c = min_max(a, c)
    b, d = min_max(b, d)
    e, g = min_max(e, g)
    f, h = min_max(f, h)
    i, k = min_max(i, k)
    j, l = min_max(j, l)
    m, o = min_max(m, o)
    n, p = min_max(n, p)
    q, s = min_max(q, s)
    r, t = min_max(r, t)
    u, w = min_max(u, w)
    v, x = min_max(v, x)
    y, aa = min_max(y, aa)
    z, bb = min_max(z, bb)
    cc, ee = min_max(cc, ee)
    dd, ff = min_max(dd, ff)
    gg, ii = min_max(gg, ii)
    hh, jj = min_max(hh, jj)
    kk, mm = min_max(kk, mm)
    ll, nn = min_max(ll, nn)

    a, e = min_max(a, e)
    b, f = min_max(b, f)
    c, g = min_max(c, g)
    d, h = min_max(d, h)
    i, m = min_max(i, m)
    j, n = min_max(j, n)
    k, o = min_max(k, o)
    l, p = min_max(l, p)
    q, u = min_max(q, u)
    r, v = min_max(r, v)
    s, w = min_max(s, w)
    t, x = min_max(t, x)
    y, cc = min_max(y, cc)
    z, dd = min_max(z, dd)
    aa, ee = min_max(aa, ee)
    bb, ff = min_max(bb, ff)
    gg, kk = min_max(gg, kk)
    hh, ll = min_max(hh, ll)
    ii, mm = min_max(ii, mm)
    jj, nn = min_max(jj, nn)

    a, i = min_max(a, i)
    b, j = min_max(b, j)
    c, k = min_max(c, k)
    d, l = min_max(d, l)
    e, m = min_max(e, m)
    f, n = min_max(f, n)
    g, o = min_max(g, o)
    h, p = min_max(h, p)
    r, u = min_max(r, u)
    t, w = min_max(t, w)
    y, gg = min_max(y, gg)
    z, hh = min_max(z, hh)
    aa, ii = min_max(aa, ii)
    bb, jj = min_max(bb, jj)
    cc, kk = min_max(cc, kk)
    dd, ll = min_max(dd, ll)
    ee, mm = min_max(ee, mm)
    ff, nn = min_max(ff, nn)

    a, y = min_max(a, y)
    b, z = min_max(b, z)
    c, aa = min_max(c, aa)
    d, bb = min_max(d, bb)
    e, cc = min_max(e, cc)
    f, dd = min_max(f, dd)
    g, ee = min_max(g, ee)
    h, ff = min_max(h, ff)
    i, gg = min_max(i, gg)
    j, hh = min_max(j, hh)
    k, ii = min_max(k, ii)
    l, jj = min_max(l, jj)
    m, kk = min_max(m, kk)
    n, ll = min_max(n, ll)
    o, mm = min_max(o, mm)
    p, nn = min_max(p, nn)

    b, c = min_max(b, c)
    d, m = min_max(d, m)
    f, k = min_max(f, k)
    g, j = min_max(g, j)
    h, v = min_max(h, v)
    i, q = min_max(i, q)
    n, o = min_max(n, o)
    s, gg = min_max(s, gg)
    x, ff = min_max(x, ff)
    z, aa = min_max(z, aa)
    bb, kk = min_max(bb, kk)
    dd, ii = min_max(dd, ii)
    ee, hh = min_max(ee, hh)
    ll, mm = min_max(ll, mm)

    d, g = min_max(d, g)
    e, s = min_max(e, s)
    f, z = min_max(f, z)
    h, dd = min_max(h, dd)
    j, m = min_max(j, m)
    k, gg = min_max(k, gg)
    o, ii = min_max(o, ii)
    p, x = min_max(p, x)
    q, y = min_max(q, y)
    v, jj = min_max(v, jj)
    bb, ee = min_max(bb, ee)
    hh, kk = min_max(hh, kk)

    d, r = min_max(d, r)
    i, q = min_max(i, q)
    k, y = min_max(k, y)
    l, v = min_max(l, v)
    m, u = min_max(m, u)
    p, dd = min_max(p, dd)
    s, cc = min_max(s, cc)
    t, bb = min_max(t, bb)
    w, kk = min_max(w, kk)
    x, ff = min_max(x, ff)

    a, i = min_max(a, i)
    b, d = min_max(b, d)
    e, q = min_max(e, q)
    g, m = min_max(g, m)
    h, t = min_max(h, t)
    k, s = min_max(k, s)
    l, n = min_max(l, n)
    o, w = min_max(o, w)
    r, z = min_max(r, z)
    u, gg = min_max(u, gg)
    v, dd = min_max(v, dd)
    x, jj = min_max(x, jj)
    aa, cc = min_max(aa, cc)
    bb, hh = min_max(bb, hh)
    ff, nn = min_max(ff, nn)
    kk, mm = min_max(kk, mm)

    c, g = min_max(c, g)
    e, i = min_max(e, i)
    f, h = min_max(f, h)
    j, t = min_max(j, t)
    k, q = min_max(k, q)
    m, y = min_max(m, y)
    n, z = min_max(n, z)
    o, aa = min_max(o, aa)
    p, bb = min_max(p, bb)
    u, ee = min_max(u, ee)
    x, dd = min_max(x, dd)
    ff, jj = min_max(ff, jj)
    gg, ii = min_max(gg, ii)
    hh, ll = min_max(hh, ll)

    b, e = min_max(b, e)
    c, q = min_max(c, q)
    d, f = min_max(d, f)
    g, s = min_max(g, s)
    j, r = min_max(j, r)
    l, p = min_max(l, p)
    m, o = min_max(m, o)
    n, t = min_max(n, t)
    u, aa = min_max(u, aa)
    v, hh = min_max(v, hh)
    w, ee = min_max(w, ee)
    x, ll = min_max(x, ll)
    y, cc = min_max(y, cc)
    z, bb = min_max(z, bb)
    ii, kk = min_max(ii, kk)
    jj, mm = min_max(jj, mm)

    c, i = min_max(c, i)
    d, k = min_max(d, k)
    f, j = min_max(f, j)
    g, m = min_max(g, m)
    h, n = min_max(h, n)
    l, r = min_max(l, r)
    o, u = min_max(o, u)
    p, v = min_max(p, v)
    s, y = min_max(s, y)
    t, z = min_max(t, z)
    w, cc = min_max(w, cc)
    aa, gg = min_max(aa, gg)
    bb, hh = min_max(bb, hh)
    dd, kk = min_max(dd, kk)
    ee, ii = min_max(ee, ii)
    ff, ll = min_max(ff, ll)

    c, e = min_max(c, e)
    g, k = min_max(g, k)
    h, l = min_max(h, l)
    m, q = min_max(m, q)
    n, r = min_max(n, r)
    o, s = min_max(o, s)
    p, t = min_max(p, t)
    u, y = min_max(u, y)
    v, z = min_max(v, z)
    w, aa = min_max(w, aa)
    x, bb = min_max(x, bb)
    cc, gg = min_max(cc, gg)
    dd, hh = min_max(dd, hh)
    jj, ll = min_max(jj, ll)

    d, e = min_max(d, e)
    f, m = min_max(f, m)
    h, o = min_max(h, o)
    j, q = min_max(j, q)
    l, u = min_max(l, u)
    n, s = min_max(n, s)
    p, w = min_max(p, w)
    r, y = min_max(r, y)
    t, cc = min_max(t, cc)
    v, aa = min_max(v, aa)
    x, ee = min_max(x, ee)
    z, gg = min_max(z, gg)
    bb, ii = min_max(bb, ii)
    jj, kk = min_max(jj, kk)

    e, i = min_max(e, i)
    f, g = min_max(f, g)
    h, k = min_max(h, k)
    j, m = min_max(j, m)
    l, n = min_max(l, n)
    o, q = min_max(o, q)
    p, u = min_max(p, u)
    r, s = min_max(r, s)
    t, y = min_max(t, y)
    v, w = min_max(v, w)
    x, z = min_max(x, z)
    aa, cc = min_max(aa, cc)
    bb, ee = min_max(bb, ee)
    dd, gg = min_max(dd, gg)
    ff, jj = min_max(ff, jj)
    hh, ii = min_max(hh, ii)

    g, i = min_max(g, i)
    h, j = min_max(h, j)
    k, m = min_max(k, m)
    l, o = min_max(l, o)
    n, q = min_max(n, q)
    p, r = min_max(p, r)
    s, u = min_max(s, u)
    t, v = min_max(t, v)
    w, y = min_max(w, y)
    x, aa = min_max(x, aa)
    z, cc = min_max(z, cc)
    bb, dd = min_max(bb, dd)
    ee, gg = min_max(ee, gg)
    ff, hh = min_max(ff, hh)

    f, g = min_max(f, g)
    h, i = min_max(h, i)
    j, k = min_max(j, k)
    l, m = min_max(l, m)
    n, o = min_max(n, o)
    p, q = min_max(p, q)
    r, s = min_max(r, s)
    t, u = min_max(t, u)
    v, w = min_max(v, w)
    x, y = min_max(x, y)
    z, aa = min_max(z, aa)
    bb, cc = min_max(bb, cc)
    dd, ee = min_max(dd, ee)
    ff, gg = min_max(ff, gg)
    hh, ii = min_max(hh, ii)

    return a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, ll, mm, nn
end


swapsort(x::NTuple{40,T}) where {T} =
     swapsort(x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19], x[20], x[21], x[22], x[23], x[24], x[25], x[26], x[27], x[28], x[29], x[30], x[31], x[32], x[33], x[34], x[35], x[36], x[37], x[38], x[39], x[40], )

swapsort(::Type{Val{40}}, x::AbstractVector{T}) where {T} =
     swapsort(x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19], x[20], x[21], x[22], x[23], x[24], x[25], x[26], x[27], x[28], x[29], x[30], x[31], x[32], x[33], x[34], x[35], x[36], x[37], x[38], x[39], x[40], )
2 Likes

Thank you very much !