Что происходит в Quicksort, если массив уже отсортирован?

@brook 

Если массив уже отсортирован, то в Quicksort будет происходить худший сценарий работы алгоритма. Это связано с тем, что Quicksort выбирает опорный элемент и перемещает все элементы, которые меньше него, в левую часть массива, а все элементы, которые больше него, в правую часть массива. В случае уже отсортированного массива, опорным элементом будет выбираться последний элемент, который уже является наибольшим элементом. В результате, все элементы будут перемещены в правую часть массива, и это будет происходить на каждом шаге разделения массива, что приведет к производительности Quicksort, очень близкой к квадратичной.