From what I can gather the middle element pivot would be better in comparison to the front element pivot if you are sorting a near sorted list. In which scenario would picking the first element as the pivot be more efficient than picking the middle element as the pivot?
I know picking Median of three is usually the best method but is there any exceptions to this that picking a fixed pivot such as the first or middle element would be more efficient?
any help would be appreciated.
From what I can gather the middle element pivot would be better in comparison to the front element pivot if you are sorting a near sorted list.
Quicksort performance is optimal when the pivot chosen for each partition happens to be the median value of the whole partition. So yes, if the input is already near-sorted, then choosing the positionwise middle element of each partition as the pivot will yield a good approximation to optimal performance. Of course, in that case an insertion sort probably does even better.
In which scenario would picking the first element as the pivot be more efficient than picking the middle element as the pivot?
If you assume that the input is uniformly random then no pivot-choice approach based on indexes alone is better or worse than any other. But for any quicksort implementation with a known, deterministic partitioning scheme, it is possible to construct inputs that elicit the worst possible behavior for that scheme. For most such partitioning schemes, wort case behavior is quadratic in the number of elements. I can't offhand describe an input that would have that effect on a middle-element-pivot quicksort,* but I assure you that there are some. Any other pivot-selection approach would provide an improvement on most such inputs.
I know picking Median of three is usually the best method
Median of three is a good approach in a wide variety of cases. As for best, it depends somewhat on what you're after.
but is there any exceptions to this that picking a fixed pivot such as the first or middle element would be more efficient?
Median-of-three is no exception to what I said above. It is possible to construct so-called "median-of-three killer" sequences that elicit worst-case behavior from an M3 quicksort, and that worst-case behavior is quadratic. Pretty much any other pivot-choice approach is better for such inputs.
On the other hand, random pivot selection is relatively common. Probabilistically, it avoids quadratic behavior, with the likelihood of going quadratic shrinking with increasing input size. And it is more or less impossible to intentionally construct a random-pivot killer sequence (doing so would require the pivot selection to rely a deterministic (pseudo-)RNG implementation whose details and initial state are known to the attacker).
On the third hand, median of medians is more complicated to implement and somewhat slower on average, but it is distinguished by imparting O(n log n) worst case behavior to an otherwise carefully implemented quicksort.
There are other alternatives.
* Inputs having most elements the same can drive many quicksort implementations quadratic, but this is not a characteristic of the pivot choice scheme, and it can be solved independently of the pivot choice scheme.