There is a significant abuse of Big Oh notation going on in this thread. “O” imposes an upper bound on the range only. When answering the OP’s question, you need to use the lower bound notation, “Big Omega”: Ω.
I.e., the information theory lower bound on sorting by comparison is Ω*(n log n)*. The upper bound O(n log n) is proven by the existence of algorithms such as Mergesort.
One thing I like about these comparison-bound arguments is the following: Finding either the min or max element takes n-1 comparisons (all but one element has to “lose” a comparison). But to find both the min and max takes ⌈3n/2⌉-2 comparisons (upper and lower bound). Somewhat of an improvement over the naive 2n-2 method. (For seem reason this seems to be a common job interview question for programmers.)
While non-trivial lower bounds are rare in Algorithm Analysis, the restriction to comparisons only helps in cases such as this.
Thank you. Good stuff. The first paper was particularly evil, designing a subversive function to compute & feed pathological data to the target sort. Obviously as an attack vector that depends on being able to inject your machine code into the execution stream.
Both papers describe the generic properties of pathological data. So that knowledge could be used offline without needing to code inject.