How to fix the "TLE" problem? I think my quicksort is OK

Question

Code:

#include<bits/stdc++.h>

using namespace std;
void quicksort(int arr[], int low, int high) {
    if (high <= low)
        return;
    int i = low;
    int j = high + 1;
    int key = arr[low];
    while (true) {
        /*Find the number that bigger than key from left to right*/
        while (arr[++i] < key) {
            if (i == high) {
                break;
            }
        }
        /*Find the number that smaller than key from right to left*/
        while (arr[--j] > key) {
            if (j == low) {
                break;
            }
        }
        if (i >= j) {
            break;
        }
        /*exchange the number of i&j*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /*exchange the number*/
    int temp = arr[low];
    arr[low] = arr[j];
    arr[j] = temp;
    quicksort(arr, low, j - 1);
    quicksort(arr, j + 1, high);
}

int main() {
    int n;
    int a[1000010];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    quicksort(a, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

Input:

5
4 5 3 1 2

Output:

1 2 3 4 5

The output is OK, and I passed 3 test points (5 for all). The other 2 test points said I used too much time. Is my code still not good? How can I upgrade it?

Answer 1

Choosing the middle value for pivot eliminates the need for bounds checking in the inner loops. This example uses two functions, but they can be combined into one function. The logic is the same:

int Partition(int arr[], int low, int high)
{
    int pivot = arr[low+(high-low)/2];
    int i = low - 1;
    int j = high + 1;
    while(1)
    {
        while(arr[++i] < pivot);
        while(arr[--j] > pivot);
        if(i >= j)
            return j;
        std::swap(arr[i], arr[j]);
    }
}

void QuickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int index = Partition(arr, low, high);
        QuickSort(arr, low, index);    /* note: not index-1 */
        QuickSort(arr, index + 1, high);
    }
}