Why is my quicksort implementation slow when given a presorted input?

Question

I'm trying to implement quicksort so I can analyze its runtime on different inputs. My implementation below runs very poorly on presorted inputs (integers in ascending order).

Given the integers 1-5000, here are the runtimes for my sort:

• Randomly ordered input: 0.052 seconds
• Descending order input: 0.065 seconds
• Ascending order input: 0.209 seconds

Given the integers 1-50000, here are the runtimes for my sort:

• Randomly ordered input: 0.585 seconds
• Descending order input: 1.598 seconds
• Ascending order input: 6.540 seconds

I'm not sure what's causing the long runtime on presorted inputs.

int median(vector<int> *input, int left, int right) {
    int mid = (right + left) / 2;
    int temp;

    // This method also orders the selected left, mid, and right values
    if ((*input)[mid] < (*input)[left]) {
        temp = (*input)[mid];
        (*input)[mid] = (*input)[left];
        (*input)[left] = temp;
    }
    if ((*input)[right] < (*input)[left]) {
        temp = (*input)[left];
        (*input)[left] = (*input)[right];
        (*input)[right] = temp;
    }
    if ((*input)[mid] < (*input)[right]) {
        temp = (*input)[mid];
        (*input)[mid] = (*input)[right];
        (*input)[right] = temp;
    }

    temp = (*input)[mid];
    (*input)[mid] = (*input)[right-1];
    (*input)[right-1] = temp;

    return (*input)[right-1];
}

void quickSort2(vector<int> *input, int left, int right) {
    if (left < right) {
        // Get pivot (median of 3)
        int pivot = median(input, left, right);
        int temp;

        int i = left, j = right - 1;
        for (; ; ) {
            while ((*input)[++i] < pivot) {}
            while (j > 0 && (*input)[--j] > pivot) {}
            if (i < j) {
                temp = (*input)[i];
                (*input)[i] = (*input)[j];
                (*input)[j] = temp;
            } else {
                break;
            }
        }

        temp = (*input)[i];
        (*input)[i] = (*input)[right - 1];
        (*input)[right - 1] = temp;

        quickSort(input, left, i - 1);
        quickSort(input, i + 1, right);
    }
}

Answer 1

Because you're using the rightmost element as a pivot and when this is done in a sorted list this results in chronically bad pivot selection. This has been covered at length: geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur

Try changing your third conditional:

if ((*input)[mid] < (*input)[right]) {

to

if ((*input)[right] < (*input)[mid]) {

Otherwsie, the swap will put the rightmost (largest) element into [mid] and then you (eventually) return it as output.

Edited for clarity