How is the efficiency of the quicksort algorithm evaluated depending on the situation?

The efficiency of the QuickSort algorithm depends on the choice of the pivot element and data structure:

• Average time: O(n log n) — with a random or well-chosen pivot.
• Worst-case time: O(n²) — if the pivot is always chosen poorly (e.g., the largest or smallest element in a sorted array).

In practice, to improve efficiency, a random pivot or median of several elements is often used.

QuickSort is usually faster than other sorting algorithms due to good data locality and low overhead, but for very small arrays or nearly sorted data, insertion sort or merge sort may be preferable.

Example of choosing a pivot:

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // simple choice of the last element
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

To improve, you can choose a random pivot or the median of three elements.