Sort a list of unknown values with the least amount of comparisons In this optimization challenge you will write a program that sorts a single array by only comparing elements through asking the user on stdout to input comparison results on stdin.

The below protocol is line-based, so everytime you print to stdout or read from stdin it is assumed a newline follows. Throughout the question below it is assumed that the user (read: the scoring program) has an array it wants sorted in a 0-based indexed array called array. For technical reasons I suggest flushing after every print to stout.


As your first step your program must read the array size n from stdin.
Then, as often as you wish, you can print a &lt; b to stdout, with two integers 0 &lt;= a, b &lt; n. Then the user will enter 1 in stdin if array[a] &lt; array[b], and 0 otherwise.
Finally, once your program is convinced it has correctly deduced the order of the array, it must print a ... to stdout, where ... is a space separated list of integers indicating the order. So if your program outputs a 3 0 1 4 2 it means your program has deduced

array[3] &lt;= array[0] &lt;= array[1] &lt;= array[4] &lt;= array[2]


Note that your program never knew the contents of array, and never will.


You can only ask for &lt; on stdin to sort the array. You can get other comparison operations by these equivalencies:

a &gt; b        b &lt; a
a &lt;= b       !(b &lt; a)
a &gt;= b       !(a &lt; b)
a != b       (a &lt; b) || (b &lt; a)
a == b       !(a &lt; b) &amp;&amp; !(b &lt; a)


Finally, since your program interacts with the scoring program on stdout, print debug information to stderr.



Your program will be scored using the following Python program:

from __future__ import print_function
from subprocess import Popen, PIPE
import sys, random

def sort_test(size):
    array = [random.randrange(0, size) for _ in range(size)]
    pipe = Popen(sys.argv[1:], stdin=PIPE, stdout=PIPE, bufsize=0, universal_newlines=True)
    print(str(size), file=pipe.stdin); pipe.stdin.flush()
    num_comparisons = 0
    while True:
        args = pipe.stdout.readline().strip().split()
        if args and args[0] == "a":
            answer_array = [array[int(n)] for n in args[1:]]
            if list(sorted(array)) != answer_array:
                raise RuntimeError("incorrect sort for size {}, array was {}".format(size, array))
            return num_comparisons
        elif len(args) == 3 and args[1] == "&lt;":
            a, b = int(args[0]), int(args[2])
            print(int(array[a] &lt; array[b]), file=pipe.stdin); pipe.stdin.flush()
            num_comparisons += 1
        else:
            raise RuntimeError("unknown command")

random.seed(0)
total = 0
for i in range(101):
    num_comparisons = sort_test(i)
    print(i, num_comparisons)
    total += num_comparisons
print("total", total)


You score your program by typing python score.py yourprogram. The scoring is done by having your program sort one random array of each size 0 to 100 and counting the amount of comparisons your program asks for. These random arrays can have duplicates, your algorithm must be able to handle equal elements. In the event there are duplicates, there are no requirements on the order of the equal elements. So if the array is [0, 0] it doesn't matter if you output a 0 1 or a 1 0.

You may not optimize specifically for the particular arrays the scoring program generates. I may change the RNG seed at any point in time. Answers using built-in sorting algorithms are permitted to be posted for interest's sake, but are non-competing.

Program with lowest score wins.
Python, score 23069

This uses the Ford–Johnson merge insertion sorting algorithm.

from __future__ import print_function
import sys

def less(x, y):
    print(x, '&lt;', y)
    sys.stdout.flush()
    return bool(int(input()))

def insert(x, a, key=lambda z: z):
    if not a:
        return [x]
    m = len(a)//2
    if less(key(x), key(a[m])):
        return insert(x, a[:m], key) + a[m:]
    else:
        return a[:m + 1] + insert(x, a[m + 1:], key)

def sort(a, key=lambda z: z):
    if len(a) &lt;= 1:
        return a
    m = len(a)//2
    key1 = lambda z: key(z[-1])
    b = sort([insert(x, [y], key) for x, y in zip(a[:m], a[m:2*m])], key=key1)
    if len(a) % 2:
        b += [[a[-1], None]]
    for k in range(m, len(a)):
        l, i, (x, y) = max((-i.bit_length(), i, t) for i, t in enumerate(b) if len(t) == 2)
        b[:i + 1] = insert([x], b[:i], key=key1) + [[y]]
    if len(a) % 2:
        b.pop()
    return [x for x, in b]

print('a', ' '.join(map(str, sort(range(int(input()))))))