Anti-sort algorithm – sort of :-)

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?




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s