Is Quicksort a potential security risk?

Question

I just wondered whether (with some serious paranoia and under certain circumstances) the use of the QuickSort algorithm can be seen as a security risk in an application.

Both its basic implementation and improved versions like 3-median-quicksort have the peculiarity of behaving deviant for certain input data, which means that their runtime can increase extremely in these cases (having O(n^2) complexity) not to mention the possibility of a stackoverflow.

Hence I would see potential to do harm by providing pre-sorted data to a programm that causes the algorithm to behave like this, which could have unpredictable consequences for e.g. a multi-client web application.

Is this strange case worth any security consideration (and would therefore force us to use Intro- or Mergesort instead)?

Edit: I know that there are ways to prevent Quicksort's worst cases, but what about language integrated sorts (like the 3-Median of .NET). Would they be taboo?

Answer 1

Yes, it is a security risk - DoS, to be specific - which is trivially mitigated by adding a check for recursion depth in your quicksort, and switching to something else instead if a certain depth is reached. If you switch to heapsort, then you'll get introsort, which is what many STL implementations actually use.

Alternatively, you just randomize the selection of pivot element.