What is the complexity of QuickSort?

QuickSort typically operates in average time O(n log n), where n is the number of elements in the array. This is achieved through recursive partitioning of the array around a pivot element, after which each subarray is sorted independently.

However, in the worst case, when the pivot element is chosen poorly (for example, always the smallest or largest element), the complexity can degrade to O(n²).

Example in C#:

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    QuickSort(arr, left, j);
    QuickSort(arr, i, right);
}

Thus, QuickSort is an efficient algorithm with good average performance, but it requires careful selection of the pivot to avoid worst-case scenarios.