I have been working on sorting algorithms for a few weeks now, but one of my question still hasn't an answer: are there optimal sequential comparison sorts for fixed-size  and random-access  collections? Most sorting algorithms adapt to the size of the collection, but knowing the size of the collection to sort allows to pick a specific sorting algorithm for this size. For example, the following algorithm should sort three values with both an optimal number of comparisons and an optimal number of swaps or assignments (it's C++, but it should be fairly easy to translate to any language):void sort3(int& x, int& y, int& z){        if (x < y) {        if (z < y) {            if (z < x) {                int tmp = z;                z = y;                y = x;                x = tmp;            } else {                std::swap(y, z);            }        }    } else if (z < y) {        std::swap(x, z);    } else if (z < x) {        int tmp = x;        x = y;        y = z;        z = tmp;    } else {        std::swap(x, y);    }}Whatever the input, this algorithm will sort three values with at most 3 comparisons and 4 assignments. I may be wrong, but I don't think that sorting three values can be done with less comparisons and less assignments than this algorithm. If it is indeed the case, then this would be an optimal comparison sorting algorithm to sort three values.It seems that optimal sorting algorithms of this kind for any size could be generated thanks to some permutation algorithm, but I was unable to find such a generation algorithm and writing one does not seem to be trivial. I tried to find near-optimal sorting algorithms for some fixed sizes, but couldn't find any simple way to generate such algorithms:Sorting networks seemed like a good idea but they always perform a fixed number of comparisons and swaps, which means that they do not adapt to the data. Even optimal sorting networks of size greater than 5 qickly lose the battle against a simple insertion sort for some inputs.Parallel sorting algorithms and non-comparison sorts (spreadsort, radix sort...) are interesting but I am interested in sequentially sorting small collections. And these categories of algorithms tend to hide a big constant complexity, which means that they are more suitable for big collections.My current method to find the most optimal sorting algorithm to sort a small fixed-size collection is to count the number of comparisons needed to sort all the possible permutations of a collection of size N:// Fill an array of size Nstd::array<int, N> collection;std::iota(std::begin(collection), std::end(collection), 0);// Count comparisons made by an insertion sortcppsort::counting_adapter<    cppsort::insertion_sorter> sorter;// Total number of comparisonsstd::size_t count = 0;// For each possible permutation of collectiondo{    auto to_sort = collection;    // Sort collection, get the number of comparisons made    count += sorter(to_sort);} while (std::next_permutation(std::begin(collection), std::end(collection)));This code uses my cpp-sort library. I used it because it makes it easy to count comparisons made by a sorting algorithm, but it could be implemented without it or in another language. This method has a problem though: it only takes into account the number of comparisons and can only help to find the most optimal algorithm amongst known algorithms, it doesn't allow to write a sorting algorithms generators.That was quite the introduction, but my question is basically as follows: are there known methods to generate sequential comparison sorting algorithms for fixed-size collections that are optimal with regards to the number of assignments and/or the number of comparisons performed?
Optimal fixed-size sequential sorting algorithms
c++;algorithms;sorting
The problem with finding the optimal algorithm is the word optimal: A sorting algorithm may be optimal in one case, but it will be suboptimal in at least one other case. The question is, what optimum you are designing it for. Take for instance your algorithm. It is optimal for the sequences:x < y <= zx >= y > z(Aside: This means that you failed to optimize the cases x == y <= z and x >= y == z properly, because they could have been handled by the same code paths. But that's not my point here.)Yet your algorithm is suboptimal for the other four possible orderings. Now, you can write algorithms like yours, that are optimal for any two of the six possible orderings (taking two comparisons), but they will all require a third comparison in the other four cases.It is simply not possible to write an algorithm that is optimal for any input order. This is true for any count of objects larger than two. That is, you have to decide, what input orderings to optimize for, and whether you have input orderings which you don't want to optimize for.To take my point a bit further: Consider the two algorithms quick-sort and insertion-sort. Can you say that either one is absolutely better than the other? No, you can't. Quick-sort will be much faster for random input, but it will simply be pawned by insertion-sort on almost sorted input. Only when you know what kind of input data to expect, you can choose one over the other.It is a bit like trying to measure location and momentum of a quantum particle. If you know one, you have no idea about the other, and vice versa. You can measure both at the same time, but then both will be inexact. Nature simply does not allow you to know both precisely at the same time. Likewise, when you compare x and y first in your algorithm, you are already breaking the symetry of the problem at hand, making optimal sorting of two thirds of the possible input sequences impossible.