# Sort StaticVector?

**URL:** <https://discourse.julialang.org/t/sort-staticvector/96591>\
**Category:** Performance\
**Tags:** staticarrays\
**Created:** [March 25, 2023, 10:29am UTC](https://discourse.julialang.org/t/sort-staticvector/96591 "2023-03-25T10:29:43Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [March 25, 2023, 10:29am UTC](https://discourse.julialang.org/t/sort-staticvector/96591/1 "2023-03-25T10:29:43Z")

</div>

Hi,

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

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [March 25, 2023, 10:42am UTC](https://discourse.julialang.org/t/sort-staticvector/96591/2 "2023-03-25T10:42:21Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [March 25, 2023, 2:53pm UTC](https://discourse.julialang.org/t/sort-staticvector/96591/3 "2023-03-25T14:53:10Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mikkoku](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikkoku/32/16274_2.png) [@mikkoku](https://discourse.julialang.org/u/mikkoku)\
**Post date:** [March 25, 2023, 3:34pm UTC](https://discourse.julialang.org/t/sort-staticvector/96591/4 "2023-03-25T15:34:59Z")

</div>

`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:

```julia
x = @SArray(rand(40))
sort(x, alg=StaticArrays.BitonicSort)

```

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [March 25, 2023, 4:03pm UTC](https://discourse.julialang.org/t/sort-staticvector/96591/5 "2023-03-25T16:03:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [March 25, 2023, 4:11pm UTC](https://discourse.julialang.org/t/sort-staticvector/96591/6 "2023-03-25T16:11:28Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![JeffreySarnoff](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeffreysarnoff/32/1980_2.png) [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)\
**Post date:** [March 31, 2023, 10:04am UTC](https://discourse.julialang.org/t/sort-staticvector/96591/7 "2023-03-31T10:04:52Z")

</div>

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 |

```julia-auto
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], )

```

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [March 31, 2023, 10:43am UTC](https://discourse.julialang.org/t/sort-staticvector/96591/8 "2023-03-31T10:43:12Z")

</div>

Thank you very much !