Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only have to split the list at most $\log_{4/3} n$. The choice of the pivot seems to be one possible problem of quicksort that can lead to $O(n^2)$ behavior.
My idea was: If in each step one would use the mean of the partition as pivot, this could increase the speed significantly. Especially after a few steps, when outliers are in their own division of the list, the mean and median should be very close to each other (once again, looking at large lists). The additional time during each step to calculate the mean should be $n$. Therefore:
Quicksort estimated time: $nA\log_{4/3} n$
Quicksort_mean estimated time: $2nA\log_{5/3} n$
(5/3 is most likely a conservative estimation by me, could as well be closer to 2, as subsets should quickly be without outliers). So, starting at around 10,000 entries Quicksort_mean would be (on average) faster than Quicksort. Furthermore, it would never risk to be $O(n^2)$, as it is bound to not take the minimal or maximal element of the stack.
My main question is: Did I miss anything? I have to admit, I never implemented quicksort myself, so I might miss out on other parts of the whole thing (storage, etc.)