This post was inspired by this news article on Intel releasing version 2.0 of their SIMD sort code:
Julia has something similar to this:
which was presented at the 2019 JuliaCon. ChipSort, however, isn’t limited to just AVX512.
While sorting is one of oldest and most studied problems in computer science. SIMD sorting algorithms appear to be the “hot new thing” right now, even though a quick search finds research on these algorithms from 1985 (Parallel Sorting Algorithms by Selim G. Akl) yet research still continues. Some research code in Julia are below:
Often different algorithms are used for the different kinds of data to be sorted (partially sorted already, unicode strings, sorting records, etc.).
Google has released a SIMD sort algorithm, vqsort:
There is an algorithm, AA-Sort (from 2007), which uses both SIMD and thread-level parallelism, but I haven’t seen a Julia implementation of it:
AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors
Here is a link to a C++ implementation of it.