u/JasonMckin

Is there any way to look at a list and measure how sorted it is?

And is there a robust way to prove that any algorithm to execute such a measurement must necessarily require n log n since the fastest sorting algorithm requires n log n?

And a final variant of these questions: is there any way to examine a list in o(n) and estimate which n lg n algorithm would sort with the least operations and likewise which n^2 algorithm would sort with the least operations?