So the worst case of quick sort is when we choose a pivot that always produces either 0 elements higher than it or 0 lower than. This happens when we use the first or last index as a pivot in a sorted array. But using the middle index, a sorted array would be divided in half in each recursive call so that it would be O(n*log(n)). But then, what is the worst case of the quick sort when we use the middle index? What situations would produce an O(n²)runtime?

Edit

I'm putting a implementation of quick sort:

partitionate(array, start, end, pivotIndex){
    pivot = array[pivotIndex];
    counter = 0;
    swap array[pivotIndex] with array[end-1];

    for index = 0; index < end; index  :
        if(array[index] <= pivot){
            swap array[index] with array[counter];
            counter  ;
        } 
  
    newPivotIndex = counter -1;

    return newPivotIndex;
}


quickSort(array, start, end) =
 {
    if(start == end) return;
    pivotIndex = floor((end-start)/2);
  
    newPivotIndex = partitionate(array, start, end, pivotIndex);
  
    quickSort(array, start, newPivotIndex);
    quickSort(array, newPivotIndex 1, end);
    
 }

CodePudding user response：

What situations would produce an O(n²)runtime?

For Lomuto partition scheme, when all elements are equal.

For any partition scheme, where the middle element is always the smallest or largest value in that partition. The data pattern to cause this to happen depends on the actual implementation.