Quick Sort Algorithm and Its Best-, Worst-, and Average-Case Time Complexities

Quick sort is a divide-and-conquer comparison sort that selects a pivot and rearranges the array so that elements smaller than the pivot come before it and larger elements come after it. The two resulting subarrays are then sorted recursively.2

Quick sort is widely studied because its expected running time is $O(n \log n)$, while its worst-case running time is $O(n^2)$. The difference comes entirely from how balanced the partitions are after each pivot selection.2

A general recurrence for quick sort is:

$$T(n)=T(k)+T(n-k-1)+\Theta(n)$$

where $k$ is the number of elements placed to the left of the pivot after partitioning, and the $\Theta(n)$ term comes from the linear-time partition step.2

Footnotes

1. Quicksort - Wikipedia - Overview of quicksort, partitioning idea, and best/average/worst-case analysis. ↩ ↩²

2. Quick Sort Algorithm - EnjoyAlgorithms - Explains quick sort pseudocode, partition cost, and recurrence-based analysis. ↩ ↩²

3. Sorting algorithm - Wikipedia - Notes that naive pivot choice can lead quicksort to $O(n^2)$ on sorted input. ↩

4. CMSC 351: QuickSort (UMD PDF) - Formal recurrence relations for partition-based quicksort analysis, including average case. ↩

Algorithm Idea

The most common classroom version uses the last element as the pivot and a partition routine such as the Lomuto partition scheme.2 The partition operation scans the subarray once, compares each element with the pivot, and swaps elements to ensure the final pivot position is correct. Since this scan is linear, partition takes $\Theta(n)$ time for a subarray of size $n$.2

If the pivot splits the array nearly equally every time, the recursion depth is about $\log_2 n$, and each level of the recursion tree performs total work proportional to $n$. Hence the total time becomes $O(n \log n)$. If the pivot is always the smallest or largest element, the recursion becomes highly unbalanced and degrades to $O(n^2)$.3

Footnotes

1. Quick Sort Algorithm - EnjoyAlgorithms - Explains quick sort pseudocode, partition cost, and recurrence-based analysis. ↩ ↩² ↩³

2. Quick Sort - GeeksforGeeks - Standard educational presentation of quick sort and example execution. ↩

3. CMSC 351: QuickSort (UMD PDF) - Formal recurrence relations for partition-based quicksort analysis, including average case. ↩

4. Quicksort - Wikipedia - Overview of quicksort, partitioning idea, and best/average/worst-case analysis. ↩

5. Sorting algorithm - Wikipedia - Notes that naive pivot choice can lead quicksort to $O(n^2)$ on sorted input. ↩

Pseudocode

A standard quick sort algorithm can be written as follows:2

1QUICKSORT(A, low, high)
2    if low < high
3        p = PARTITION(A, low, high)
4        QUICKSORT(A, low, p - 1)
5        QUICKSORT(A, p + 1, high)
6
7PARTITION(A, low, high)
8    pivot = A[high]
9    i = low - 1
10
11    for j = low to high - 1
12        if A[j] <= pivot
13            i = i + 1
14            swap A[i] and A[j]
15
16    swap A[i + 1] and A[high]
17    return i + 1

This version sorts in-place except for recursion stack usage, which is one reason quick sort is popular in practice.2

Footnotes

1. Quicksort - Wikipedia - Overview of quicksort, partitioning idea, and best/average/worst-case analysis. ↩ ↩²

2. Quick Sort Algorithm - EnjoyAlgorithms - Explains quick sort pseudocode, partition cost, and recurrence-based analysis. ↩

3. Sorting algorithm - Wikipedia - Notes that naive pivot choice can lead quicksort to $O(n^2)$ on sorted input. ↩

Example Walkthrough

Consider the array:

$$[10, 7, 8, 9, 1, 5]$$

Using the last element $5$ as the pivot, partitioning places all elements $\le 5$ to its left and all larger elements to its right. One possible result after the first partition is:

$$[1, 5, 8, 9, 10, 7]$$

Now the pivot $5$ is in its final sorted position. Quick sort recursively processes the left subarray $[1]$ and the right subarray $[8, 9, 10, 7]$. Repeating this process eventually sorts the full array.2

Footnotes

1. Quick Sort Algorithm - EnjoyAlgorithms - Explains quick sort pseudocode, partition cost, and recurrence-based analysis. ↩

2. Quick Sort - GeeksforGeeks - Standard educational presentation of quick sort and example execution. ↩

Time Complexity Analysis

The running time depends on the partition sizes produced at each recursive call.2

1. Best Case

The best case occurs when each pivot divides the array into two nearly equal halves.2

The recurrence is:

$$T(n)=2T\left(\frac{n}{2}\right)+\Theta(n)$$

By the Master Theorem or recursion-tree reasoning:

$$T(n)=O(n \log n)$$

Reason:

• There are about $\log_2 n$ levels of recursion.
• Each level performs total partition work of $\Theta(n)$.2

So:

$$\text{Best-case time complexity} = O(n \log n)$$

2. Worst Case

The worst case occurs when the pivot is always the smallest or largest element, producing partitions of sizes $0$ and $n-1$.2

The recurrence is:

$$T(n)=T(n-1)+\Theta(n)$$

Expanding:

$$T(n)=\Theta(n)+\Theta(n-1)+\Theta(n-2)+\cdots+\Theta(1)$$

Thus:

$$T(n)=O(n^2)$$

So:

$$\text{Worst-case time complexity} = O(n^2)$$

3. Average Case

The average case assumes pivot positions are reasonably distributed over recursive calls. Mathematical analyses show that the expected number of comparisons is proportional to $n \log n$.2

A representative recurrence is:

$$T(n)=T(k)+T(n-k-1)+\Theta(n)$$

averaged over all possible pivot positions $k=0,1,\dots,n-1$. This yields:

$$T(n)=O(n \log n)$$

So:

$$\text{Average-case time complexity} = O(n \log n)$$

Footnotes

1. Quicksort - Wikipedia - Overview of quicksort, partitioning idea, and best/average/worst-case analysis. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. CMSC 351: QuickSort (UMD PDF) - Formal recurrence relations for partition-based quicksort analysis, including average case. ↩ ↩² ↩³

3. Quick Sort Algorithm - EnjoyAlgorithms - Explains quick sort pseudocode, partition cost, and recurrence-based analysis. ↩ ↩²

4. Sorting algorithm - Wikipedia - Notes that naive pivot choice can lead quicksort to $O(n^2)$ on sorted input. ↩

Final Answer

The algorithm for quick sort is:

1QUICKSORT(A, low, high)
2    if low < high
3        p = PARTITION(A, low, high)
4        QUICKSORT(A, low, p - 1)
5        QUICKSORT(A, p + 1, high)

with partition:

1PARTITION(A, low, high)
2    pivot = A[high]
3    i = low - 1
4    for j = low to high - 1
5        if A[j] <= pivot
6            i = i + 1
7            swap A[i], A[j]
8    swap A[i + 1], A[high]
9    return i + 1

Its time complexities are:

• Best case: $O(n \log n)$ when the pivot divides the array into nearly equal halves.2
• Average case: $O(n \log n)$ in the expected sense over pivot positions or input permutations.2
• Worst case: $O(n^2)$ when the pivot repeatedly produces splits of sizes $0$ and $n-1$.2

Thus, the standard result is:

$$\boxed{\text{Best} = O(n \log n),\quad \text{Average} = O(n \log n),\quad \text{Worst} = O(n^2)}$$

Footnotes

1. Quicksort - Wikipedia - Overview of quicksort, partitioning idea, and best/average/worst-case analysis. ↩ ↩² ↩³

2. Quick Sort Algorithm - EnjoyAlgorithms - Explains quick sort pseudocode, partition cost, and recurrence-based analysis. ↩

3. CMSC 351: QuickSort (UMD PDF) - Formal recurrence relations for partition-based quicksort analysis, including average case. ↩

4. Sorting algorithm - Wikipedia - Notes that naive pivot choice can lead quicksort to $O(n^2)$ on sorted input. ↩