What is the worst-case time complexity of quicksort?

The worst-case time complexity of the QuickSort algorithm is O(n²), where n is the number of elements being sorted.

The worst-case scenario occurs when the pivot element is chosen such that the array is divided very unevenly — for example, when the pivot is always the smallest or largest element, resulting in one partition containing n-1 elements and the other containing 0.

In this case, recursion becomes a series of linear scans through the array, leading to quadratic complexity.

However, on average and in the best case, QuickSort operates in O(n log n) time, making it very efficient in practice.

Here's an example in C# (without pivot selection optimizations):

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[right];
    int partitionIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] < pivot) {
            int temp = arr[i];
            arr[i] = arr[partitionIndex];
            arr[partitionIndex] = temp;
            partitionIndex++;
        }
    }
    arr[right] = arr[partitionIndex];
    arr[partitionIndex] = pivot;

    QuickSort(arr, left, partitionIndex - 1);
    QuickSort(arr, partitionIndex + 1, right);
}

If the input data is already sorted or nearly sorted, and the pivot is poorly chosen (for example, always the last element), then the complexity will be O(n²).