The size of the output is n^2. So you do need at least that much effort. But it's not O(n lg n) to sort n^2 items, it'd be O(n^2) to just construct the output a

The size of the output is n^2. So you do need at least that much effort. But it's not O(n lg n) to sort n^2 items, it'd be O(n^2) to just construct the output and then O(n^2 lg n) to sort it. So there is potentially a lg n to shave off there.