Quick Sort MCQs test more than O(n log n): you must read the pivot's split, form a recurrence, or count comparisons. Common slips are using the average case when asked for the worst case, missing why a first or last pivot makes sorted input bad, and losing track of comparison counts.
GATE previous-year questions examine Quick Sort through pivots, recurrences, worst cases, and comparison counts. Attempt each one before reading its explanation, then use the Quick Sort PYQ hub for the rest.
How Quick Sort partitions: the one mechanic behind every question
Quick Sort picks a pivot, partitions smaller elements to its left and larger ones to its right, then recurses. There is no merge step because partitioning puts the pivot in its final position.
For A = [7, 2, 1, 6, 8, 5, 3, 4], use the last element, 4, as a Lomuto pivot. Scanning swaps 2, 1 and 3 forward; the final pivot swap gives [2, 1, 3, 4, 8, 5, 7, 6]. Pivot 4 is fixed at index 3, leaving {2, 1, 3} and {8, 5, 7, 6} to sort.
Runtime follows the block balance. A near-median pivot divides evenly; an extreme pivot leaves one block nearly full-sized.
Best, average, and worst case: what the pivot decides
Best-case balanced pivots produce Θ(log n) recursion depth and Θ(n log n) total work. Random pivots give Θ(n log n) expected time, while repeated extreme pivots produce Θ(n²) worst-case time through subproblems of sizes n - 1, n - 2, and so on.
Q1. GATE 2016. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
(a) Theta(n log n), Theta(n log n) and Theta(n^2)
(b) Theta(n^2), Theta(n^2) and Theta(n log n)
(c) Theta(n^2), Theta(n log n) and Theta(n log n)
(d) Theta(n^2), Theta(n log n) and Theta(n^2)
Answer: (d). Insertion Sort is Theta(n^2) on reverse-sorted input. Merge Sort stays Theta(n log n), while repeated 0-and-(n - 1) splits make Quick Sort Theta(n^2).
Q2. GATE 2007. Which of the following sorting algorithms has the lowest worst-case complexity?
(a) Merge sort
(b) Bubble Sort
(c) Quick Sort
(d) Selection Sort
Answer: (a) Merge sort. Merge Sort guarantees O(n log n) worst-case time; the other three can require O(n^2). Quick Sort's fast average case is the trap.
(a) O(n^2)
(b) O(n log n)
(c) Theta(n log n)
(d) O(n^3)
Answer: (a) O(n^2). A central index need not hold a central value. Repeated extreme values give T(n) = T(n - 1) + Theta(n) = Theta(n^2), so option (c) is false.
(a) O(n)
(b) O(n log n)
(c) O(n^2)
(d) O(n!)
Answer: (c) O(n^2). Random pivots make repeated extreme choices unlikely, not impossible. Expected time is O(n log n), but worst-case time remains O(n^2).
Smarter pivots and the recurrences they create
Read the split ratio and write its recurrence. A larger side bounded below n by a constant fraction keeps depth logarithmic.
(a) O(n^2 log n)
(b) O(n^2)
(c) O(n log n log n)
(d) O(n log n)
Answer: (d) O(n log n). The median makes two halves, while selection plus partitioning costs O(n). Thus T(n) = 2T(n/2) + O(n); with a = b = 2, the Master Theorem gives Theta(n log n).
(a) Theta(n)
(b) Theta(n log n)
(c) Theta(n^2)
(d) Theta(n^2 log n)
Answer: (b) Theta(n log n). The split gives T(n) = T(n/4) + T(3n/4) + Theta(n). The larger side remains a constant fraction below n, producing logarithmic depth and Theta(n log n) total work.
(a) T(n) <= 2 T(n/5) + n
(b) T(n) <= T(n/5) + T(4n/5) + n
(c) T(n) <= 2 T(4n/5) + n
(d) T(n) <= 2 T(n/2) + n
Answer: (b). The sides range from n/5 to 4n/5, so the bound pairs those extremes and adds linear partition work. The other options assume unpromised symmetric splits.
Counting comparisons by hand
A block of size k needs k - 1 pivot comparisons. Add that cost across the recursive calls.
(a) t1 = 5
(b) t1 < t2
(c) t1 > t2
(d) t1 = t2
Answer: (c) t1 > t2. Sorted input gives t1 = 4 + 3 + 2 + 1 = 10. For the second input, pivot 4 costs 4 and its three-element side costs 2 + 1 = 3, so t2 = 7. Therefore 10 > 7.
(a) Selection sort
(b) Mergesort
(c) Insertion sort
(d) Quicksort using the last element as pivot
Answer: (c) Insertion sort. Sorted input gives Insertion Sort n - 1 = 7 comparisons. Selection Sort makes 8 x 7 / 2 = 28, and last-pivot Quick Sort makes 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28. Standard top-down Merge Sort makes 4 + 4 + 4 = 12 across its three merge levels, so 7 wins.
(a) I and II only
(b) I and III only
(c) II and IV only
(d) I and IV only
Answer: (d) I and IV only. A first or last pivot makes Quick Sort Theta(n^2), while Insertion Sort is Theta(n). Optimised Bubble Sort stops after one swap-free pass, and Merge Sort stays Theta(n log n).
Quick Sort against the field: swaps and the sorting lower bound
Data movement and the lower bound obeyed by every comparison sort are important Quick Sort topics.
Q11. GATE 2006. Which one of the following in-place sorting algorithms needs the minimum number of swaps?
(a) Quick sort
(b) Insertion sort
(c) Selection sort
(d) Heap sort
Answer: (c) Selection sort. One swap per pass gives Selection Sort at most n - 1 swaps. Quick Sort swaps during partitioning, while Heap Sort swaps during heap maintenance. Comparison count and swap count are different measures.
Q12. GATE 2004. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
(a) n
(b) n^2
(c) n log n
(d) n log^2 n
Answer: (c) n log n. A comparison decision tree needs at least n! leaves. Since height h permits at most 2^h leaves, 2^h >= n! and h >= log2(n!) = Theta(n log n). Quick Sort cannot beat this worst-case order.
How Quick Sort is examined, and the short version
The three exam habits are matching complexity to pivot behaviour, writing split recurrences, and counting comparisons. Watch for worst-case wording and sorted input with a first or last pivot.
Redo your two weakest questions after a week. Continue with GATE Guidance by Sanchit Sir, place Algorithms through the GATE CS Exam category, or build the placement angle through MERN Stack + DSA.
For Q1, Q2, Q9 and Q11, read Sorting Algorithms: Complexity and Comparison. Next, try Data Structures MCQs, then drill the remaining questions in the Quick Sort PYQ hub.
