My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem?
In more details: we know that sorting using comparison have the achievable lower bound of $O(n\ln n)$ where $n$ is the number of items to be sorted. Now the question of superlinear and sublinear is dependent on what is considered the size of the input, and I am not sure if $n$ is the size here. We have 2 cases:
(a) The input is a full acyclic graph describing the comparison relation. In this case the input size is actually $O(n^{2})$ and the problem is sublinear.
(b) The input is just the item to be sorted, plus the description of a Turing machine that will perform the comparison. Then the input size is $O(n)$ and the problem is superlinear.
Can anyone clarify what is the consensus on this? Some people tell me that sorting with comparison is an example of a problem with a nontrivial lower bound (ie. the lower bound stronger than just by looking at how much information do the algorithm need to know). However, it seemed to me that in fact this is one example where figure out how much information you need is the crux of the problem, and not any combinatorial nature of Turing machine. Thanks.