Heap sort is an examiner favourite because one procedure tests three facts: a guaranteed O(n log n) worst case, in-place sorting and inherent instability. ISRO, RSSB, DSSSB, GATE, Coal India, BPSC and TCS have all set questions on those facts, or on how heap sort differs from bubble, insertion, selection and merge sort. Attempt each one before reading its explanation, and open the Algorithms learn module if the heap basics feel shaky.
How heap sort actually runs, worked once
Heap sort first builds a max-heap in O(n). It then repeats three actions n-1 times: swap the root with the last unsorted element, shrink the heap by one, and sift the new root down in O(log n).
Take A = [12, 11, 13, 5, 6, 7], with 0-based indexing and n = 6. Build the heap by sifting from i = 2 down to 0:
i = 2: 13 is greater than its child 7, so nothing moves.
i = 1: 11 is greater than children 5 and 6, so nothing moves.
i = 0: 12 is smaller than child 13. Swap them, then stop because 12 is greater than child 7.
The max-heap is [13, 11, 12, 5, 6, 7]. The extraction rounds are:
[12, 11, 7, 5, 6 | 13]
[11, 6, 7, 5 | 12, 13]
[7, 6, 5 | 11, 12, 13]
[6, 5 | 7, 11, 12, 13]
[5 | 6, 7, 11, 12, 13]
The sorted array is [5, 6, 7, 11, 12, 13]. A heap has height floor(log n), so a sift takes at most O(log n). Root-to-last swaps can make equal elements cross, which is why heap sort is unstable. For a wider comparison, use Sorting Algorithms: Complexity, Stability, n log n Bound.
![Max-heap of [13, 11, 12, 5, 6, 7] as a binary tree beside the five extraction rounds that sort the array to [5, 6, 7, 11, 12, 13].](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1784134249564_e05sjo.jpg)
The worst-case complexity family
ISRO, DSSSB and RSSB each set the same fact from a different direction: two ask for heap sort's worst case outright, the third asks which algorithm guarantees n log n.
Q1. ISRO 2023 (solved page)
Worst case time complexity of heap sort for n elements?
(a) O(n log n)
(b) O(log n)
(c) O(n^2)
(d) O(n)
Answer: (a). Building the heap costs O(n), and each of up to n extraction rounds costs at most O(log n). Therefore O(n log n) holds for every input, unlike quicksort, whose O(n log n) average can become O(n^2) in the worst case.
Q2. DSSSB 2018 (solved page)
What is the worst-case time complexity of the Heap sort?
(a) O(n)
(b) O(n^2)
(c) O(n log n)
(d) O(n^3)
Answer: (c). This is Q1 with the correct fact moved to another option. Derive the complexity before looking at the letters, since papers can shuffle the same choices.
Q3. RSSB 2018 (solved page)
Which of the following sorting algorithms has the worst time complexity of n log(n)?
(a) Heapsort
(b) Quicksort
(c) Insertion sort
(d) Selection sort
Answer: (a). Quicksort can reach n^2, while insertion sort and selection sort also have n^2 worst cases. Heapsort alone in this list guarantees n log n. Read "worst time complexity of n log n" as the guaranteed ceiling rather than the typical running time, because quicksort averages n log n as well and still fails this question.
Heap sort in Theta(log n) time: the GATE 2013 trap
Q4. GATE 2013 (solved page)
The number of elements that can be sorted in Θ(log n) time using heap sort is
(a) Θ(1)
(b) Θ(√(log n))
(c) Θ(log n / log log n)
(d) Θ(log n)
Answer: (c). Sorting k elements costs Theta(k log k), so set k log k = Theta(log n). For k = log n / log log n, log k = log log n - log log log n = Theta(log log n), and the log log n factors cancel. Option (d) costs Theta(log n log log n), which is too large, while a constant k costs Theta(1). Substitution is faster and safer here than trying to solve the equation directly.
Stability and the cost of swaps
Q5. Coal India 2020 (solved page)
Consider the following statements
Insertion Sort and Merge Sort are stable.
Heap Sort is inherently unstable.
Selection Sort is not inherently stable, but may be coded in such a way that it is stable.
(a) Only statement 1 is correct
(b) All statements are correct
(c) Statement 3 is not correct
(d) Only statement 1 and 2 is correct
Answer: (b). Standard insertion and merge sort preserve the order of equal keys. Heap sort can move equal keys past each other through non-adjacent swaps. Selection sort's usual long swap is unstable, but replacing it with an insertion-style shift can preserve order, so all three statements hold.
Q6. Concept
Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?
(a) Heap Sort
(b) Selection Sort
(c) Insertion Sort
(d) Merge Sort
Answer: (b). Selection sort places one item per pass with at most one swap, giving at most n-1 swaps. Heap sort swaps during extraction and can swap repeatedly while sifting, reaching O(n log n) swaps in the worst case. This matters when writes are much costlier than comparisons, as with flash memory.
Heap sort against the rest of the family
Q7. Concept
Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.
(a) Insertion Sort
(b) Heap Sort
(c) Merge Sort
(d) Selection Sort
Answer: (a). In insertion sort, no earlier element is strictly greater than the key, so the inner loop never shifts anything and the run takes O(n). Heap sort still performs all extraction rounds, merge sort still recurses and merges, and selection sort still scans every remaining suffix. The reusable fact is that already sorted input is insertion sort's O(n) best case.
Q8. TCS 2026 (solved page)
______ Sorting compares two adjoining values and exchanges them if they are not in proper order.
(a) Heap
(b) Selection
(c) Insertion
(d) Bubble
Answer: (d). Comparing and exchanging adjoining values is bubble sort's fingerprint. Heap sort compares parents with children, selection sort searches for an extreme value, and insertion sort shifts a key left past larger values. Match the behavioural phrase before checking the options.
Q9. BPSC TGT 2023 (solved page)
Which of the following is a divide-and-conquer algorithm?
(a) Merge sort
(b) Heap sort
(c) Bubble sort
(d) More than one of the above
(e) None of the above
Answer: (a). Merge sort splits the array, sorts both halves recursively, and merges them. Heap sort organises the array as a heap rather than splitting it into independent subproblems, while bubble sort is iterative. Exactly one option qualifies, so (d) and (e) also fail.
Quicksort's worst case: the same reasoning transferred
The last question asks about quicksort rather than heap sort, and the reasoning is the same one Q1 to Q3 rewarded: work out whether the algorithm can actually reach its bad case instead of recalling a formula.
Q10. GATE 1996 (solved page)
Quicksort is run on two inputs shown below to sort in ascending order taking the first element as pivot,
(i) 1, 2, 3, ..., n
(ii) n, n-1, n-2, ..., 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
(a) C1 < C2
(b) C1 > C2
(c) C1 = C2
(d) We cannot say anything for arbitrary n
Answer: (c). In both inputs, the first pivot is an extreme value, so each partition is maximally lopsided. The comparison count is (n-1) + (n-2) + ... + 1 = n(n-1)/2 in each run, hence C1 = C2. Disorder is not the issue here, partition balance is.
How exams test heap sort: the short version
Worst-case time is O(n log n) for every input. Building the heap is O(n), and one sift is bounded by the heap height, floor(log n).
For Q4, set k log k equal to Θ(log n), then substitute k = log n / log log n.
Heap sort is unstable. When swaps are expensive, remember selection sort's maximum of n-1 swaps.
Adjacent exchange means bubble sort, all-equal input favours insertion sort, and divide and conquer points to merge sort.
Worst-case reasoning transfers to quicksort: sorted and reverse-sorted inputs are equally bad with the first element as pivot.
Use Binary Tree MCQs: 11 Solved BST, AVL, Heaps next if you want to practise heaps from the tree side. Every GATE and PSU question above is solved with video inside GATE Guidance by Sanchit Sir, while the same sorting ideas for company tests are covered in Coding for Placements.
