# How fast can we sort a list if we know how it was written?

Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the list that $G$ outputs for input size $n$.

In general, can we compute sparse-sort(G,n) asymptotically faster than $O(n \log n)$?

It's easy to generate examples where we can manage linear time, for example any $G$ that runs $G(n-1)$, then appends some predictable value to the list. Likewise, it seems plausible that one could use the function $G$ in the algorithm to get a good runtime in general.

• It depends a bit on what you mean - if you only count comparisons then, according to your definition there is a unique output for every n, which means that there exists an algorithm that doesn't use any comparisons at all... but I'm guessing that wasn't what you meant - so there has to be some reasonable reformulation of the model here. – daniello Sep 26 '17 at 15:55
• I'd like an algorithm that runs for every pair $G \times n$, or perhaps for a fixed $G$ and every $n$. We can't memorize the output for every $n$, the table is too big! – Artimis Fowl Sep 26 '17 at 16:50
• @MarzioDeBiasi the output of G should be a list of length $n$ of any integers in a reasonable format. Not necessarily $[n]$ to avoid radix sort answers, and probably not in unary because that usually takes longer than $O(n)$ time to write. – Artimis Fowl Sep 27 '17 at 14:38
• Ok! Now it's clear! – Marzio De Biasi Sep 27 '17 at 14:39