Description
The current fixed-size sorting_network_sorter uses size-optimal sorting networks: sorting networks that use the smallest known number of comparators. However; other sorting networks may be interesting:
- Depth-optimal sorting networks, where the depth corresponds to the number of parallel steps needed to sort a collection. The best-known depth-optimal networks have more comparators than size-optimal networks (see Sorting Networks: to the End and Back Again).
- Swap-optimal sorting networks: even when two sorting networks have the same depth and/or the same number of comparators, they may perform a different number of swaps on average to sort a collection (see Introduction to Sorting Networks, slide 29).
A first step would be to rename sorting_network_sorter into size_optimal_network_sorter and to introduce the new fixed-size depth_optimal_network_sorter and swap_optimal_network_sorter. However, the names are a bit long and typing them might be a bit tedious. An open question would be: while every sorter has an optimality criterion, what should be the second criterion? For example, size_optimal_network_sorter uses size-optimal networks, but when there are several size-optimal networks, should it use the most depth-optimal one or the most swap-optimal one?
A more evolved solution would be to keep sorting_network_sorter and give it an additional template parameter Optimality corresponding to an enum struct with the values size, depth and swaps. Even more complete: make it take two parameters for optimality (variadic in a far future?) to choose the most important criterions for optimality. From a back-end point of view, there would be a collection of sorting networks with associated size, depth and swaps properties and we could plug an insane template system to dispatch a call to the sorting network whose properties are the closest to those wanted (inb4 madness). Unfortunately, passing more template parameters to a fixed-size sorter means that it doesn't compose well with small_array_adapter (how do you pass the non-size parameters? No matter how you see it it seems ugly), so a clean solution should be found to mitigate everything.