Formula & Calculator
Quick Sort Average-Case Time Complexity
Estimates the number of operations quicksort performs on average, reflecting its O(n log n) expected time complexity.
Interpretation
Quick sort average‑case time complexity is O(n log n). It partitions the array around a pivot and recursively sorts the sub‑arrays. Example: For n=1,000,000, average comparisons are roughly 1e6 × log₂(1e6) ≈ 20 million.
Variables
| Symbol | Quantity | Unit |
|---|---|---|
| T(n) | Estimated operation count | |
| n | Number of elements |
What it means
Quick sort is a highly efficient, divide‑and‑conquer sorting algorithm that works by selecting a pivot element and partitioning the array into elements less than and greater than the pivot, then recursively sorting the subarrays. On average, the pivot divides the array into two roughly equal halves, resulting in a recurrence T(n) = 2T(n/2) + O(n), which solves to O(n log n). The average case is often achieved with random pivot selection or using the median‑of‑three method to avoid worst‑case behavior. In practice, quick sort is one of the fastest sorting algorithms and is used in many standard libraries (e.g., C’s qsort, Java’s Arrays.sort for primitives). However, its worst‑case time complexity is O(n²) when the pivot is poorly chosen (e.g., already sorted data with a fixed first‑element pivot). It is an in‑place sort requiring O(log n) stack space for recursion. Quick sort is not stable, but its speed and low memory overhead make it a favorite for general‑purpose sorting.
Worked example
Quick Sort Average‑Case – Two Examples
Real‑World| Parameter | Value |
|---|---|
| n | 1000 |
| n·log₂(n) | 1000×9.966 ≈ 9,966 |
| Parameter | Value |
|---|---|
| n | 1,000,000 |
| n·log₂(n) | 1,000,000×19.93 ≈ 19.93 million |
Common mistakes
- Average‑case only: Quick sort has O(n log n) on average, but worst‑case is O(n²) when the pivot is poorly chosen (e.g., sorted input with first/last pivot).
- Pivot selection: Random or median‑of‑three pivot reduces the chance of worst‑case; deterministic choices can be exploited.
- In‑place: Quick sort is in‑place, but it uses O(log n) stack space for recursion (average).
- Stability: Quick sort is not stable unless modified.
- Constants: The constant factor for quick sort is lower than merge sort, so it is often faster in practice despite same asymptotic complexity.
Applications
Quick sort is a highly efficient, divide‑and‑conquer sorting algorithm with an average‑case time complexity of O(n log n), but worst‑case O(n²). Its average‑case performance makes it one of the most widely used sorting algorithms in practice, especially in standard libraries (e.g., C's `qsort`, Java's `Arrays.sort` for primitives). Quick sort is favoured for its in‑place sorting and good cache locality, making it suitable for large datasets in memory. It is used in database systems, data processing pipelines, and any application requiring fast, general‑purpose sorting. Understanding its average‑case complexity helps engineers choose appropriate pivot strategies (e.g., random, median‑of‑three) and recursion depth limits to avoid worst‑case behaviour.
- General‑purpose sorting in programming libraries
- In‑memory sorting of large arrays
- Data processing and analytics (e.g., map‑reduce)
- Selection algorithms (quickselect)
- Algorithm design and complexity analysis
Frequently Asked Questions
The average‑case time complexity of quicksort is O(n log n), specifically approximately 1.39 n log₂ n comparisons. This is derived from the recurrence T(n) = 2T(n/2) + O(n) when the pivot splits the array into roughly equal halves on average.
The worst‑case is O(n²), which occurs when the pivot selection is unbalanced – e.g., always picking the smallest or largest element as pivot (when the array is already sorted, and pivot is the first or last element). In such cases, one subarray has size 0 and the other has n‑1, leading to n‑1 levels of recursion, each doing O(n) work.
The best‑case occurs when the pivot divides the array into two equal halves at every recursion level. Then T(n) = 2T(n/2) + O(n), which solves to O(n log n). The recurrence is exactly the same as merge sort, but with a smaller constant factor in practice.
The pivot choice is critical:
- First/last element: O(n²) on sorted arrays.
- Random pivot: gives O(n log n) with high probability, avoiding worst‑case behavior.
- Median‑of‑three: improves the average by choosing a better pivot, reducing the constant factor.
Quicksort is an in‑place sorting algorithm (it modifies the original array) but requires O(log n) stack space for the recursion (in the best/average case) and O(n) in the worst case (when recursion is unbalanced). The space is used for the recursion call stack. Iterative versions can reduce this to O(log n).
Quicksort is generally faster than merge sort for in‑memory sorting because it has better cache locality and lower constant factors (fewer moves). However, it is not stable, and its worst‑case O(n²) is a concern unless randomized. Merge sort is stable and guaranteed O(n log n), making it preferred for certain applications (e.g., sorting objects with multiple keys).
- Pivot selection – using a fixed pivot (first/last) on already sorted data leads to O(n²).
- Stack overflow – for large arrays, recursion depth can be large; use tail‑call optimization or iterative version.
- Not handling duplicates well – the classic Hoare partition can get stuck with many equal elements; use a three‑way partition (Dutch national flag) to handle duplicates efficiently.
- Incorrect partitioning – off‑by‑one errors are common; carefully test the partition logic.
The average‑case recurrence gives T(n) = 2T(n/2) + O(n), which has a hidden constant. The number of comparisons on average is about 2 n ln n ≈ 1.39 n log₂ n, compared to merge sort’s n log₂ n (but merge sort does more moves). This lower constant is why quicksort is often faster in practice.
If the array has many duplicates, the standard quicksort may degrade to O(n²) if the partition puts all equal elements on one side. A three‑way partition (＜, ＝, ＞) groups equal elements together, making it O(n) in the case of all equal elements. This is often used in languages like Java (Dual‑Pivot Quicksort).
- C library’s qsort() – though not necessarily quicksort, many implementations use it.
- Java’s Arrays.sort() – uses a dual‑pivot quicksort for primitive types.
- Python’s sorting – Timsort is a hybrid, but quicksort is used in some contexts.
- Database query sorting – often uses external sorting, but quicksort is used for in‑memory sorts.