> There's literally no such thing as a hard wall where something is nlogn in time and can't get lower

I guess you're saying that this holds in "realistic" computational models? Sorting in the decision tree model is famously \Omega(n log n)-time.