A sort of anti-sort algorithm could be:
1. Given the ordered set of criteria keys, sort the data set D. (I believe) this will place all records in a way that minimizes Hamming distance between successive entries
2. Split the resultant array in half with top half named T (t1, t2, …, tn) and bottom half named B (b1, b2, …, bn)
3. Invert B – call it B’ (so that b1 becomes b’n, b2 becomes b’n-1, …, bn becomes b’1)
4. Now make an anti-sorted data set A with elements in this order t1, b’1, t2, b’2, …, tn, b’n
If my conjecture in #1 is correct, B’s bottom will be the most distant from T’s top and as we come towards the center, the distance should go down.
That means A will have most distanced record at the top and as you go down, distance diminishes. What an ideal way of picking test cases!
Can someone prove the algorithm please?