How to Test a System Designed to Sort Four Numbers Using Only Five Comparisons?

I have a system to sort four numbers using a sequence of five comparisons. The system uses a series of 'MinMax' comparator boxes that take in two numbers and output the minimum and maximum. My configuration is as follows:

1. I use two MinMax boxes in parallel to compare a & b and c & d initially.
2. The minimum and maximum outputs from those boxes are then fed into two more MinMax boxes to determine the overall minimum and maximum.
3. The second minimum and second maximum are then compared using a final MinMax box.

The system is designed to sort any given sequence of four numbers with these five comparisons. However, I am concerned about potential failures in the system - if one of the MinMax boxes were to malfunction, for instance.

I would like to devise a test to ensure that all components of the system are functioning correctly. My question is: What is the minimal sequence of numbers that I can input to verify the integrity of the system, and why those sequence? I'm looking for a sequence that would efficiently test all MinMax boxes and connections in the system.
(There is a similar question that ask how to sort, not how to test. https://stackoverflow.com/questions/6145364/sort-4-number-with-few-comparisons)

In order to test sorting function exhaustively, you have to create input samples with all possible relations between their elements.<br>For N=4 some samples might look like this:

{{C},{B},{A},{D}}  →  (С<B) & (B<A) & (A<D)  →  [2,1,0,3]
{{A,D},{B,C}}      →  (A=D) & (D<B) & (B=C)  →  [0,1,1,0]
{{B},{A,C,D}}      →  (B<A) & (A=C) & (C=D)  →  [1,0,1,1]

Here elements of the same group {} are equal, but greater than elements of previous groups.

Total number of ordered partitions of equality groups is 2^N-1, all of which you have to work through.<br>In your case there will be 8 partitions:

{1,1,1,1}
{1,1,2}
{1,2,1}
{2,1,1}
{1,3}
{2,2}
{3,1}
{4}

So for each partition, you have to iterate over all possible disjoint sets of N elements.<br>For example, for the partition {2,2} there're 6 such combinations:

{{A,B},{C,D}}
{{A,C},{B,D}}
{{A,D},{B,C}}
{{B,C},{A,D}}
{{B,D},{A,C}}
{{C,D},{A,B}}

Then, in order to get concrete numbers, it's enough to set a value of 0 for the elements of the first group, and increase it by 1 for the elements of each subsequent group. This will create actual samples of N elements, each resulting in a unique ordering for a given partition:

{{A,B},{C,D}}  →  [0,0,1,1]
{{A,C},{B,D}}  →  [0,1,0,1]
{{A,D},{B,C}}  →  [0,1,1,0]
{{B,C},{A,D}}  →  [1,0,0,1]
{{B,D},{A,C}}  →  [1,0,1,0]
{{C,D},{A,B}}  →  [1,1,0,0]

When you're done with all partitions, you'll have a complete unit test for your algorithm (provided that it behaves coherently regardless of specific arithmetic properties of the numbers being sorted).

If you don't like doing it by hand, the following snippet will generate all samples for N=4 (75 in total):

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function generateSamples (length, callback) {

    // test sample
    let sample = new Uint32Array(length);

    // doubly linked list of unused indices in sample
    let unused = [];
    let unusedHead = 0;
    let unusedCount = length;
    for (let i = 0; i < length; i++) {
        unused.push({ index: i, prev: null, next: null });
    }
    for (let i = 1; i < length; i++) {
        unused[i - 1].next = unused[i];
        unused[i].prev = unused[i - 1];
    }

    // list of group sizes
    let partition;

    // flag for callback
    let newPartition;

    // recurse groups
    function processNextGroup (groupId) {

        // proceed to the next group
        if (groupId < partition.length) {
            processNextElement(groupId, partition[groupId], unused[unusedHead], unusedCount - partition[groupId] + 1);
        }

        // the final group is exhausted, the sample is complete
        else if (newPartition) {
            newPartition = false;
            callback(sample.slice(), `{${partition.join(',')}}`);
        }
        else {
            callback(sample.slice(), false);
        }
    }

    // recurse group elements
    function processNextElement (groupId, groupSize, indexItem, variants) {

        // iterate over remaining variants for the current element
        for (let i = 0; i < variants; i++, indexItem = indexItem.next) {

            // unlink index item from the list
            if (indexItem.prev) {
                indexItem.prev.next = indexItem.next;
            }
            else {
                unusedHead = indexItem.next?.index;
            }
            if (indexItem.next) {
                indexItem.next.prev = indexItem.prev;
            }

            // update current sample element
            sample[indexItem.index] = groupId;

            // recurse...
            unusedCount--;
            if (groupSize > 1) {
                // ... to the next element
                processNextElement(groupId, groupSize - 1, indexItem.next, variants - i);
            }
            else {
                // ... to the next group
                processNextGroup(groupId + 1);
            }
            unusedCount++;

            // return index item to the list
            if (indexItem.prev) {
                indexItem.prev.next = indexItem;
            }
            else {
                unusedHead = indexItem.index;
            }
            if (indexItem.next) {
                indexItem.next.prev = indexItem;
            }
        }
    }

    // generate partitions by iterating bitmaps
    // - 1-bit: current element starts new group
    // - 0-bit: current element continues the last group
    let maxBitmap = 2 ** (length - 1);
    for (let bitmap = 0; bitmap < maxBitmap; bitmap++) {

        partition = [];
        let groupSize = 1;
        for (let pos = length - 2; pos >= 0; pos--) {
            if ((bitmap >>> pos) & 1) {
                partition.push(groupSize);
                groupSize = 1;
            }
            else {
                groupSize++;
            }
        }
        partition.push(groupSize);
        newPartition = true;

        // generate every combination of the current partition
        processNextGroup(0);
    }
}

let lastSignature;
let samples;
let samplesAll = [];

function logSamples (caption, samples) {
    console.log(caption);
    console.log(`[\n  [${samples.join('],\n  [')}]\n]`);
}

generateSamples(4, (sample, newSignature) => {
    if (newSignature) {
        if (samples) {
            logSamples(`Partition = ${lastSignature}`, samples);
        }
        lastSignature = newSignature;
        samples = [];
    }
    samples.push(sample);
    samplesAll.push(sample);
});
logSamples(`Partition = ${lastSignature}`, samples);
logSamples(`ALL SAMPLES: ${samplesAll.length}`, samplesAll);

<!-- end snippet -->

PS: The function generateSamples can generate larger sets for whatever reasons. I tested it up to N=9 which yielded 7,087,261 combinations. Internally it uses O(N) space and generates each sample in O(N) time.

Thanks to the zero-one principle of sorting networks, if your sorting algorithm can be viewed as a sorting network (a composition of MinMax boxes as you call them is pretty much the definition of a sorting network) it suffices to check all binary inputs, of which there are only 2⁴=16 in this case.

Those inputs correspond to the numbers 0..15 (which would be fed into the algorithm as 4 separate bits, not one number) so the algorithm to generate the sequence of inputs is trivial.

There are 4!=24 permutations of (1,2,3,4). It is easy to enumerate them. If your system sorts some of them incorrectly, then it is broken. If it sorts all of them correctly, we can claim that it correctly sorts permutations of (1,2,3,4). This inspires confidence in its correct functioning, but cannot prove it. Indeed, what if one of your boxes compares 23002936894782192854 and 94528594871170264370, and only this pair, incorrectly? It is impossible to weed out all such failure modes without checking all permutations of all 4-tuples of numbers, and there are infinitely many of those.