I'm trying to understand why quicksort using Lomuto partition and a fixed pivot is performing erratically, but overall poorly, on randomly generated inputs.  I'm thinking that even though the inputs are randomly generated, there may be a lot of order to the sequences, but I'm not sure how to measure the level of disorder in the sequences.  I thought about using the number of inversions, but I saw from this other question I asked that that's not really a good measure in this case.The reason I suspect that my random sequences have a lot of order to them is that randomizing the pivot fixes the performance problem.  But theoretically there shouldn't be any performance problem on these supposedly random input sequences.
What Measure of Disorder to use when Analysing Quicksort
algorithms;sorting