Robin Hood sort

[jariji]

Just for interest - I found this sort that looks good for some applications. https://github.com/mlochbaum/rhsort

[LilithHafner]

Thanks for sharing! It's always fun to see new sorting algorithms :)

A quick test using rhsort's benchmarks indicates it's about 2x slower than Julia's default on its own benchmarks on my machine, which is still faster than almost all non-Julia sorting algorithms.

x@x dev % git clone https://github.com/mlochbaum/rhsort && cd rhsort
Cloning into 'rhsort'...
remote: Enumerating objects: 406, done.
remote: Counting objects: 100% (48/48), done.
remote: Compressing objects: 100% (40/40), done.
remote: Total 406 (delta 9), reused 39 (delta 8), pack-reused 358
Receiving objects: 100% (406/406), 242.29 KiB | 1.25 MiB/s, done.
Resolving deltas: 100% (227/227), done.
x@x rhsort % gcc bench.c -o bench && ./bench && git rev-parse HEAD     
In file included from bench.c:80:
./rhsort.c:170:25: warning: while loop has empty body [-Wempty-body]
  while (aux[--sz] == s); sz++;
                        ^
./rhsort.c:170:25: note: put the semicolon on a separate line to silence this warning
1 warning generated.
Sorting random 4-byte integers: rhsort
Testing size     1000: best: 10.000 avg: 16.526 ns/v
Testing size    10000: best: 10.600 avg: 12.569 ns/v
Testing size   100000: best: 12.530 avg: 13.271 ns/v
Testing size  1000000: best: 16.825 avg: 18.294 ns/v
944ad9dc4b8f0d16dcdb471b9eaf99856c3fd0f0
x@x rhsort % julia -e 'using BenchmarkTools, Random, Printf, InteractiveUtils
       for n in 10 .^ (3:6)
           v = rand(Int32, n)
           result = @benchmark sort($v) setup=(rand!($v)) evals=1 gctrial=false samples=3e7/n
           @printf "Testing size %8i: best: %6.3f avg: %6.3f ns/v\n" n minimum(result.times)/n mean(result.times)/n
       end
       versioninfo()'
Testing size     1000: best:  5.125 avg:  7.125 ns/v
Testing size    10000: best:  4.546 avg:  5.722 ns/v
Testing size   100000: best:  4.622 avg:  5.174 ns/v
Testing size  1000000: best:  5.010 avg:  5.280 ns/v
Julia Version 1.9.1
Commit 147bdf428cd (2023-06-07 08:27 UTC)
Platform Info:
  OS: macOS (arm64-apple-darwin22.4.0)
  CPU: 8 × Apple M2
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, apple-m1)
  Threads: 1 on 4 virtual cores

[LilithHafner]

I was misusing rhsort. It is actually quite fast on its own benchmarks, however, it unfortunately does not support sorting 64-bit floating point numbers so I can't add it this this repo.