Median Sort timer 40s memory 1024MB

You want to sort \mathbf{N} distinct items, x_1, x_2, \dots, x_\mathbf{N}. Unfortunately, you do not have a way of comparing two of these items. You only have a way to, given three of them, find out which one is the median, that is, which one is neither the minimum nor the maximum among the three.

For example, suppose \mathbf{N} = 5 and you know that:

• x_1 is the median of \{x_1, x_2, x_3\}
• x_2 is the median of \{x_2, x_3, x_4\}
• x_3 is the median of \{x_3, x_4, x_5\}

Then, it is guaranteed that the sorted order of the elements is either x_4, x_2, x_1, x_3, x_5 or its reverse x_5, x_3, x_1, x_2, x_4. Notice that by knowing only medians, it is impossible to distinguish the order of any list from its reverse, since the median question has the same result for any three elements in both cases.

Your program will have to find the order of \mathbf{T} lists of \mathbf{N} elements using at most \mathbf{Q} median questions in total (or \mathbf{Q} / \mathbf{T} queries per list on average). In each case, finding either the right order or its reverse is considered correct. The order for each case is generated uniformly at random from all possible orders, and independently of any other information.