I search a little bit online but I didn't find much, my question is on an input with dimension n, what's the probability of the worse case occurring in the quicksort algorithm). I know it's quite rare but I was wondering numerically speaking how much it was and how can we evaluate it. Thank you

CodePudding user response：

The worst case for quick sort, is when the chosen element (pivot) is always the smallest/biggest element in the remaining set.

To generate such sequence - you need to work recursively, each step creating two arrays on both sides of your last pivot, where the pivot which was chosen previously was the biggest or the smallest one, so the recursive algorithm of QS split the array into the worst case where one side was 0.