# \[ANN\] OptimalSortingNetworks: Sort small collections efficiently and with good type inference

**URL:** <https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544>\
**Category:** Package Announcements\
**Tags:** package, announcement, tuple, sort, vector\
**Created:** [October 29, 2023, 5:06pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544 "2023-10-29T17:06:39Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 29, 2023, 5:06pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/1 "2023-10-29T17:06:39Z")

</div>

[OptimalSortingNetworks](https://gitlab.com/nsajko/OptimalSortingNetworks.jl) (OSN for short) is [being](https://github.com/JuliaRegistries/General/pull/94338) registered. Use it to sort small tuples or vectors:

```julia-repl
julia> using OptimalSortingNetworks

julia> sorted([10, 5, 7, 9])
4-element Vector{Int64}:
  5
  7
  9
 10

julia> sorted((10, 5, 7, 9))
(5, 7, 9, 10)

julia> sorted(reverse ∘ minmax, (10, 5, 7, 9))
(10, 9, 7, 5)

julia> const new_mm = OptimalSortingNetworks.new_minmax
new_minmax (generic function with 2 methods)

julia> sorted(new_mm(less = >), (10, 5, 7, 9))
(10, 9, 7, 5)

julia> tup = ((key=3, val="a"), (key=1, val="b"), (key=2,val="c"))
((key = 3, val = "a"), (key = 1, val = "b"), (key = 2, val = "c"))

julia> sorted(new_mm(by = (n -> n.key)), tup)
((key = 1, val = "b"), (key = 2, val = "c"), (key = 3, val = "a"))

julia> sorted(new_mm(by = (n -> n.key), less = >), tup)
((key = 3, val = "a"), (key = 2, val = "c"), (key = 1, val = "b"))

```

`sorted` does not qualify as a _stable_ sort, i.e., the order among identical elements will not necessarily be preserved.

I intend to create another package for tuple sorting in general, which will probably use merge sort with a dependency on OSN for the base cases of the recursion. EDIT [ANN](https://discourse.julialang.org/t/ann-tuplesorting-sort-tuples-efficiently-and-with-good-type-inference/105756)

EDIT: vectors are now supported, in addition to tuples

---

<div class="post-metadata">

**Author:** ![Krastanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krastanov/32/6817_2.png) [@Krastanov](https://discourse.julialang.org/u/Krastanov)\
**Post date:** [October 29, 2023, 5:13pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/2 "2023-10-29T17:13:40Z")

</div>

For folks like me who did not know what a Sorting Network is: [Sorting network - Wikipedia](https://en.wikipedia.org/wiki/Sorting_network)

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [October 29, 2023, 6:20pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/3 "2023-10-29T18:20:45Z")

</div>

Could it also be used as an algorithm for Base `sort`? cc @Lilith

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 29, 2023, 6:23pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/4 "2023-10-29T18:23:48Z")

</div>

Yeah, it could be useful as a performance optimization. Most of the effort for a PR would probably come down to careful benchmarking to find good thresholds for switching to sorting networks.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [October 29, 2023, 8:26pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/5 "2023-10-29T20:26:04Z")

</div>

This seems to be significantly faster than Base’s tuple sorting in both runtime and compile time.

```julia
julia> for i in 1:20
           println(i)
           x = Tuple(rand(i))
           @time sort(x)
           @time sorted(x)
           @btime sort($x)
           @btime sorted($x)
       end
1
  0.001746 seconds (2.28 k allocations: 108.430 KiB, 98.43% compilation time)
  0.001823 seconds (3.61 k allocations: 169.359 KiB, 99.16% compilation time)
  1.375 ns (0 allocations: 0 bytes)
  1.375 ns (0 allocations: 0 bytes)
2
  0.003862 seconds (14.96 k allocations: 756.289 KiB, 99.35% compilation time)
  0.002913 seconds (5.99 k allocations: 292.672 KiB, 99.49% compilation time)
  1.666 ns (0 allocations: 0 bytes)
  1.375 ns (0 allocations: 0 bytes)
3
  0.005494 seconds (20.86 k allocations: 1.080 MiB, 99.44% compilation time)
  0.002853 seconds (11.49 k allocations: 585.125 KiB, 99.53% compilation time)
  3.083 ns (0 allocations: 0 bytes)
  1.666 ns (0 allocations: 0 bytes)
4
  0.010172 seconds (42.30 k allocations: 2.316 MiB, 99.74% compilation time)
  0.003560 seconds (14.91 k allocations: 772.594 KiB, 99.47% compilation time)
  4.208 ns (0 allocations: 0 bytes)
  2.166 ns (0 allocations: 0 bytes)
5
  0.013185 seconds (38.95 k allocations: 2.096 MiB, 99.78% compilation time)
  0.003609 seconds (21.28 k allocations: 1.079 MiB, 99.51% compilation time)
  7.083 ns (0 allocations: 0 bytes)
  3.916 ns (0 allocations: 0 bytes)
6
  0.026137 seconds (65.27 k allocations: 3.628 MiB, 99.88% compilation time)
  0.004008 seconds (26.30 k allocations: 1.329 MiB, 99.60% compilation time)
  8.625 ns (0 allocations: 0 bytes)
  5.250 ns (0 allocations: 0 bytes)
7
  0.025794 seconds (51.51 k allocations: 2.736 MiB, 99.88% compilation time)
  0.005348 seconds (32.75 k allocations: 1.734 MiB, 99.71% compilation time)
  9.926 ns (0 allocations: 0 bytes)
  6.958 ns (0 allocations: 0 bytes)
8
  0.038604 seconds (67.09 k allocations: 3.516 MiB, 99.93% compilation time)
  0.005249 seconds (37.66 k allocations: 1.988 MiB, 99.66% compilation time)
  16.241 ns (0 allocations: 0 bytes)
  8.334 ns (0 allocations: 0 bytes)
9
  0.022513 seconds (55.22 k allocations: 3.057 MiB, 99.88% compilation time)
  0.006660 seconds (47.14 k allocations: 2.506 MiB, 99.82% compilation time)
  19.664 ns (0 allocations: 0 bytes)
  11.094 ns (0 allocations: 0 bytes)
10
  0.329988 seconds (1.23 M allocations: 67.375 MiB, 99.99% compilation time)
  0.009091 seconds (56.44 k allocations: 2.971 MiB, 99.72% compilation time)
  50.489 ns (2 allocations: 144 bytes)
  13.598 ns (0 allocations: 0 bytes)
11
  0.014698 seconds (79.00 k allocations: 4.314 MiB, 99.69% compilation time)
  0.009332 seconds (62.86 k allocations: 3.298 MiB, 99.85% compilation time)
  60.568 ns (2 allocations: 144 bytes)
  15.364 ns (0 allocations: 0 bytes)
12
  0.018018 seconds (83.03 k allocations: 4.528 MiB, 99.71% compilation time)
ERROR: MethodError: no method matching sorted(::OptimalSortingNetworks.var"#2#3"{typeof(identity), typeof(<)}, ::NTuple{12, Float64}, ::Depth)

Closest candidates are:
  sorted(::Any, ::NTuple{10, Any}, ::Union{Depth, Size})
   @ OptimalSortingNetworks ~/.julia/packages/OptimalSortingNetworks/MzN3U/src/OptimalSortingNetworks.jl:111
  sorted(::Any, ::Union{Tuple{}, Tuple{Any}, Tuple{Any, Any}, Tuple{Any, Any, Any}, NTuple{4, Any}, NTuple{5, Any}, NTuple{6, Any}, NTuple{7, Any}, NTuple{8, Any}, NTuple{9, Any}, NTuple{11, Any}}, ::Union{Depth, Size})
   @ OptimalSortingNetworks ~/.julia/packages/OptimalSortingNetworks/MzN3U/src/OptimalSortingNetworks.jl:106
  sorted(::Any, ::NTuple{10, Any})
   @ OptimalSortingNetworks ~/.julia/packages/OptimalSortingNetworks/MzN3U/src/OptimalSortingNetworks.jl:111
  ...

Stacktrace:
 [1] sorted(t::NTuple{12, Float64}, o::Depth)
   @ OptimalSortingNetworks ~/.julia/packages/OptimalSortingNetworks/MzN3U/src/OptimalSortingNetworks.jl:99
 [2] macro expansion
   @ ./timing.jl:282 [inlined]
 [3] top-level scope
   @ ./REPL[7]:5

```

PRs to base welcome 🙂

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [October 29, 2023, 8:34pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/6 "2023-10-29T20:34:37Z")

</div>

Does this have any difficult-to-remedy weaknesses compared to SortingNetworks.jl or is it a strict win?

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 29, 2023, 9:04pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/7 "2023-10-29T21:04:46Z")

</div>

It should be a strict win. There’s nothing deeply wrong with the SortingNetworks package (except for the fact that `minmax` is hardcoded instead of a parameter), but creating a new package seemed easier than trying to address the couple of perceived issues with SortingNetworks, given that the algorithms are trivial anyway.

One thing to note is that my style was to code each sorting network in a sort of single-assignment form, I figured that each variable being assigned to only once could help the compiler’s type inference when the tuple is heterogeneous. SortingNetwork instead uses the minimal number of local variables. I’m not totally sure of the implications of one vs the other implementation approach.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 30, 2023, 6:02am UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/8 "2023-10-30T06:02:24Z")

</div>

FTR, it crossed my mind that it would make sense to support static vectors in addition to tuples, because an `SArray` is basically just a `Tuple` in a wrapper with additional type annotations. However then I realized that StaticArrays already supports some sorting functionality. Given that circular dependencies are nonsensical (two packages can’t depend on eachother, I think), I’ll instead try to make StaticArrays depend on OptimalSortingNetworks, to improve the SA sort performance (glancing at their code, it seems like it could be improved in both small and large cases).

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [October 30, 2023, 9:55am UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/9 "2023-10-30T09:55:11Z")

</div>

> [@nsajko](#):
>
> SortingNetwork instead uses the minimal number of local variables. I’m not totally sure of the implications of one vs the other implementation approach.

For homogeneous tuples of subtypes of `Real` (which is the only kind supported by SortingNetworks) it probably makes no difference at all once Julia has transformed it to SSA form. At least `@code_typed sorted((1, 2, 3))` and `@code_typed swapsort((1, 2, 3))` look structurally identical.

> [@nsajko](#):
>
> Given that circular dependencies are nonsensical (two packages can’t depend on eachother, I think)

I’m not sure how you arrived at the circular dependency, but this looks like an ideal case for a package extension.

You could also consider a convenience function for sorting of short (standard) vectors. SortingNetworks sort of (pun intended) supports that except that it somewhat weirdly returns a tuple.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 30, 2023, 10:46am UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/10 "2023-10-30T10:46:55Z")

</div>

> [@GunnarFarneback](#):
>
> no difference at all once Julia has transformed it to SSA form

Thanks, I supposed it works like that but wasn’t sure.

> [@GunnarFarneback](#):
>
> I’m not sure how you arrived at the circular dependency, but this looks like an ideal case for a package extension.

StaticArrays already implements one sorting algorithm (`<:Base.Sort.Algorithm`). I think it would make sense to add another one (based on merge sort and OSN for the base cases) to StaticArrays, but then I couldn’t depend on SA from OSN,

> [@GunnarFarneback](#):
>
> consider a convenience function for sorting of short (standard) vectors

I want to do this, but need to be careful to prevent run time dispatch.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [October 30, 2023, 11:12am UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/11 "2023-10-30T11:12:22Z")

</div>

> [@nsajko](#):
>
> I want to do this, but need to be careful to prevent run time dispatch.

I would try something like this, with or without metaprogramming:

```julia-auto
sorted(x::AbstractVector) = sorted!(copy(x))

function sorted!(x::AbstractVector)
    if length(x) == 1
        x .= sorted((x[1],))
    elseif length(x) == 2
        x .= sorted((x[1], x[2]))
    elseif length(x) == 3
        x .= sorted((x[1], x[2], x[3]))
    else
        error("Vector too long.")
    end
    return x
end

```

Edit: Feel free to optimize out the one element case. 🙂

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 30, 2023, 9:05pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/12 "2023-10-30T21:05:42Z")

</div>

> [@GunnarFarneback](#):
>
> I would try something like this, with or without metaprogramming:
> 
> ```julia
> sorted(x::AbstractVector) = sorted!(copy(x))
> 
> function sorted!(x::AbstractVector)
> 
> ```

Now the package supports sorting vectors. The interface currently allocates and copies a new vector, I should probably try to also add a mutable sort, something like your `sorted!`. Just have to think about how to do it in the nicest way possible, not sure whether to just add a new function or something else.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [October 30, 2023, 9:35pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/13 "2023-10-30T21:35:44Z")

</div>

Yeah, it loses some of the charm of having a super fast `Vector` sort algorithm if you can’t do it in place.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 31, 2023, 4:23pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/14 "2023-10-31T16:23:31Z")

</div>

Added `sorted!`, but it allocates even though it works in-place. I think this is due to a bug in Julia:

[https://github.com/JuliaLang/julia/issues/51955](https://github.com/JuliaLang/julia/issues/51955)

EDIT: `sorted!` doesn’t allocate any more now (when applied to homogeneous vectors), thanks to workaround/fix provided by @Lilith

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [February 25, 2024, 6:59pm UTC](https://discourse.julialang.org/t/ann-optimalsortingnetworks-sort-small-collections-efficiently-and-with-good-type-inference/105544/15 "2024-02-25T18:59:05Z")

</div>

> [@jar1](#):
>
> Could it also be used as an algorithm for Base `sort`?

Not ideal for a default sort because it’s unstable, but it could be another algorithm for `sort(;alg=SortingNetwork())`.