Also check out the first response for a nice explanation and an optimization to eliminate the branch. The author replaced it with a bit twiddling solution to either store the current element or zero if it is less than 128 in a temporary variable and then always add that to the sum.
It's not obviously easy either. You won't know if an arbitrary collection is already sorted unless you check each element.
The middle (median) element in a sorted array has only less elements on the left and greater elements on the right, so the first pass of the quicksort would do nothing and not recurse further.
Or am I missing something?
4 3 2 1 5 9 8 7 6Still, probably faster to incorporate a monotonic check in a quicksort first pass, than run a bubble-sort pass which probably won't help much anyway?
edit: which means it does not need a do nothing first pass and takes mitigating actions only in the worst case.