★ /prog/ challenge No. 666 ★ (Easy)

THE CHALLENGE:
Implement ``Tohosort'' (http://www.freewebs.com/tohosort/) ^{66in Lisp99} in your programming language of choice.

Post the source code of your implementation. It should at least read the input from stdin and print a sorted list after making the comparisons.

Deadline: 2013-01-21 00:00.

The programs will be judged by elegance, speed and number of comparisons made using a random list that will be published the day of the deadline. The winner will be awarded with Ten (10) שקליםSuss (that's Suss-shekels for you goyim), which is enough to pay the fee needed to cross the Sanzu River by ferry.

List of ordered pairs '(a b) representing a > b
Function (trans) that adds pairs to the list according to the transitive property of >
Function (compare a b) that returns #t if '(a b) is in the list and #f if '(b a) is in the list. If neither pair is in the list it asks the user to solve the comparison and adds it to the list.

Plug compare into your favorite comparative sort algorithm for a first try.


This method will produce decent results, but you can do way better. For example starting with a single elimination tournament to get a binary tree to straighten out. I'm guessing an element higher on the list will usually beat one that's lower on the tree. I think this sort of predictive method would minimize the comparisons you need to ask the user.

Another interesting idea is using heuristics to guess preference. Probably the approach I would prefer.