Difficulty: Intermediate | Prerequisites: Sorting algorithms basics, recursion, Big-O notation, understanding of partitioning
QuickSort's performance depends entirely on how well the pivot divides the array. In COSC 3320, this question tests whether you can construct specific array arrangements that force QuickSort into its best or worst case, given a fixed pivot selection rule (here: always pick the first element). This is less about coding QuickSort and more about understanding the relationship between data arrangement, pivot choice, and recursion depth. You need to be comfortable with the concept of balanced vs unbalanced partitions.
For optimal QuickSort (pivot = first element, equal-size partitions every time), arrange the array so the first element is always the median of the current subarray. For worst-case QuickSort, use an already-sorted array so the pivot is always the minimum, producing maximally unbalanced partitions. The exam requires you to construct a concrete example with n >= 13.
Pivot
The element chosen to partition the array. All elements less than or equal to the pivot go left; all elements greater than or equal go right. In this problem, the pivot is always A[lo], the first element of the current subarray.
Partition
The operation that rearranges elements around the pivot, producing two subarrays. Think of it as the single most important step in QuickSort: everything else is just recursion.
Balanced partition
A partition where the two resulting subarrays are roughly equal in size. This is the best case for QuickSort and yields O(n log n) time.
Unbalanced partition
A partition where one subarray is much larger than the other (worst case: one subarray has n-1 elements, the other has 0). This yields O(n^2) time.
Median
The middle value when elements are sorted. If the pivot is always the median of the subarray, every partition is perfectly balanced.
The pivot is always A[lo], the first element of the subarray being sorted. After partitioning, all elements in A[lo:m] are <= pivot and all elements in A[m:hi] are >= pivot.
For equal-size partitions at every level, the first element must be the median of the subarray. The construction works recursively:
Start with the numbers 1 to 13
The median of {1, 2, ..., 13} is 7. Place 7 first.
Left half {1, 2, 3, 4, 5, 6}: median is 4. Place 4 first in the left portion.
Right half {8, 9, 10, 11, 12, 13}: median is 11 (or 10). Place it first in the right portion.
Continue recursively for each sub-half.
The exam answer constructs: 7, 1, 3, 2, 5, 6, 4, 11, 8, 10, 9, 12, 13
Verification (traced in the exam):
Pivot = 7, splits into [4, 1, 3, 2, 5, 6] and [11, 8, 10, 9, 12, 13]
Left: pivot = 4, splits into [2, 1, 3] and [4, 5, 6]
Right: pivot = 11, splits into [9, 8, 10] and [11, 12, 13]
Each level produces equal-size halves, giving O(n log n) performance
The worst case occurs when the pivot is always the smallest (or largest) element, producing one empty subarray and one of size n-1. The simplest construction is an already-sorted array:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
At each step, the pivot (first element) is the minimum. After partitioning, the left subarray is empty and the right subarray has n-1 elements. This gives n levels of recursion with O(n) work each, yielding O(n^2) total.
T_{\text{best}}(n) = 2\,T\!\left(\frac{n}{2}\right) + O(n) = O(n \log n)T_{\text{worst}}(n) = T(n-1) + O(n) = O(n^2)The best-case recurrence arises when the pivot splits the array in half each time. The worst-case recurrence arises when the pivot lands at one extreme, leaving a subarray of size n-1.
Most standard-library sorting implementations use a variant of QuickSort (or introsort, which falls back to heapsort if QuickSort's recursion gets too deep). The pivot selection strategy directly affects real performance: production implementations use median-of-three or random pivots to avoid worst-case behaviour on nearly-sorted data.
Students often think QuickSort's worst case is rare in practice. With first-element pivot selection, any sorted or nearly-sorted input triggers it, and sorted data is very common.
Students sometimes confuse "median of the array" with "median of three." Median-of-three picks the median of the first, middle, and last elements. True median selection would require O(n) preprocessing.
A common mistake on the exam is constructing an optimal-case array that does not actually produce equal partitions. You must verify by tracing through the partition step.
Students sometimes think a reverse-sorted array avoids the worst case. With first-element pivot, reverse-sorted is equally bad: the pivot is always the maximum.
The exam will ask you to construct a specific array. Practice building optimal-case arrays recursively for various values of n.
You must show your work: trace the partition at each level to prove the partitions are equal-sized.
Know both the best-case and worst-case recurrences cold. Be ready to derive them from the partition structure.
True or False: An already-sorted array gives the best-case performance for QuickSort with first-element pivot.
Fill in the blank: For optimal QuickSort, the first element of every subarray should be the ___ of that subarray.
True or False: QuickSort's worst-case time complexity is O(n log n).
Fill in the blank: For n = 13, the optimal pivot for the full array is ___.
Q: For n = 7, construct an array of the numbers 1 to 7 that gives optimal QuickSort performance when the pivot is always the first element.
A: The median of {1, 2, 3, 4, 5, 6, 7} is 4. Left half {1, 2, 3}: median is 2. Right half {5, 6, 7}: median is 6. Array: 4, 2, 1, 3, 6, 5, 7.
Q: Why does a sorted array produce worst-case QuickSort when the pivot is the first element?
A: The first element of a sorted array is always the minimum. After partitioning, the left subarray is empty and the right subarray has n-1 elements. This produces n levels of recursion, each doing O(n) work for a total of O(n^2).
Q: Could a reverse-sorted array also be worst-case for first-element pivot?
A: Yes. The first element is always the maximum, so after partitioning, the right subarray is empty and the left has n-1 elements. The recursion depth and total work are identical to the sorted case.
Q: What is the recursion depth for the optimal case with n = 13?
A: log2(13) rounded up, which is 4 levels. Each level does O(n) partitioning work, giving O(n log n) total.
This connects to the divide-and-conquer paradigm covered in the Towers of Hanoi question. The recurrence analysis uses the same Master Theorem approach. It also connects to selection algorithms (finding the k-th smallest element), since optimal pivot selection is equivalent to median finding. In later coursework, randomised QuickSort and its expected-case analysis build directly on these foundations.
QuickSort, quick sort, pivot selection, partition, median pivot, first element pivot, best case QuickSort, worst case QuickSort, O(n log n), O(n^2), balanced partition, unbalanced partition, divide and conquer, sorting algorithms, in-place sort, COSC 3320