How to make worst case permutation of median of three quicksort
algorithm, c++, data-structures, sorting
Solution
It's not really possible to create an arrangement of items that will cause all or even most Quicksort implementations to exhibit worst-case behavior. And in fact, depending on how the sort is implemented, a worst-case array on one run might be just fine on a subsequent run. That could happen if the implementation used a median-of-random-three to pick the pivot, and used a different seed each time the routine were called.
The C `qsort` function, and the sort library functions from many other libraries, are vulnerable to a "Quicksort killer" algorithm, though, that uses the information provided in the comparison callback to create a worst case scenario on the fly. It's surprisingly not difficult to do. See, for example, A Killer Adversary for Quicksort.
Problem
I know time complexity of Quick sort. But I want to know how to create worst case permutation. I guess there is a rule to make it. I thought it really much, but too difficult to me. Please tell me how to create worst case for median of three quick sort, NOT JUST NORMAL QUICK SORT. (for example, if pivot is most left side item in list, worst case permutation of list is sorted list, but how about pivot is median of three?) here is my quick sort algorithm code