CareerCup

If we have something like a1 > a2, a2 > a3, a3 > a1, we know that there is no ascneding order. So we can create a graph based on the comparisons. Create nodes for each element. and then if element x > element y, direct the graph from node y to x. Run some sort of graph algorithm like DFS with cycle detection. If we detect a cycle, we know that we can not order in ascending order.

I think this can be done by topology sort , if a1 > a2 then draw an edge from a2 to a1, using this way to setup a graph, then do a topology sort for the problem

Sort in ascending order of the first elements using quick sort. Then try to find the location of the second element in the sorted list using binary search on the right hand side of its greater number.

You may also sort the second part and then do one time merge. In any of these methods the running time will be O(n log n), because you have n/2 items that you don't know their order.