No.282

問い合わせ回数が制限されているが, 1度の問い合わせで複数の比較を行うことができる.

たとえば, 8個の要素があったときに, これを {1,2,3,4},{5,6,7,8} と分け,

• {1,5}, {2,6}, {3,7}, {4,8}
• {1,6}, {2,7}, {3,8}, {4,5}
• {1,7}, {2,8}, {3,5}, {4,6}
• {1,8}, {2,5}, {3,6}, {4,7}

で問い合わせを行う.

次にさらに {1,2},{3,4},{5,6},{7,8} と分け,

• {1,3},{2,4},{5,7},{6,8}
• {1,4},{2,3},{5,8},{6,7}

で問い合わせを行う.

これを繰り返すことですべての要素対の大小関係を $N-1$ 回の問い合わせで判定できる.

これですべての要素対の大小関係がわかったので, あとはクイックソートなりを使ってソートすればいい.