That wouldn't work for general n, but for smaller n, optimized sorting libraries frequently use size-optimal sorting networks [1] which effectively do the same

That wouldn't work for general n, but for smaller n, optimized sorting libraries frequently use size-optimal sorting networks [1] which effectively do the same thing (partitioning permutations into two halves with the minimal size difference). [1] https://en.wikipedia.org/wiki/Sorting_network#Optimal_sorting_networks https://en.wikipedia.org/wiki/Sorting_network#Optimal_sortin...