---
title: "Heap sort with example"
subject: "Data Structure and Algorithm"
chapter: 7
key: "semester_4/data_structure_and_algorithm:heap-sort-example"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/heap-sort-example
site: BCT Engineering
---

# Heap sort with example

Data Structure and Algorithm · Chapter 7: Sorting

- Asked in: 2069 Bhadra, 2+6 marks
- Video: [L-3.18: Heap sort with Example | Heapify Method](https://www.youtube.com/watch?v=nJ6FdAIr_6g) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/heap-sort-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7

## Question

Differentiate internal and external sorting. Explain heap sort with an appropriate example.

## Short answer

Internal sorting fits all data in RAM; external sorting handles data on disk with sequential block access. Heap sort builds a max-heap in O(n), then repeatedly swaps root with the last heap element and sifts down. Example sorted: 12,25,33,37,48,57,86,92. Time O(n log n), space O(1).

## Answer

#### Internal and external sorting
| Internal sorting | External sorting |
|---|---|
| All data fits in main memory (RAM) | Data is too large and is kept on disk or tape |
| Direct access to any element | Data is read in blocks; access is sequential/block-wise |
| Examples: bubble, quick, heap, insertion sort | Examples: external merge sort, polyphase merge |
| Cost is measured in comparisons | Cost is dominated by disk I/O operations |

#### Heap sort
**Heap sort** uses a max-heap: an almost complete binary tree in which every parent is ≥ its children, stored in an array (children of index i at 2i+1 and 2i+2). 

Algorithm:
1. Build a max-heap from the array (heapify from the last parent n/2 − 1 down to 0).
2. Swap the root (largest) with the last element of the heap, and reduce the heap size by one. The largest element is now in its final place.
3. Restore the heap property by sifting the new root down.
4. Repeat steps 2–3 until only one element remains.

```c
void sift(int a[], int i, int n) {            /* sift a[i] down in heap of size n */
    int l, g, t;
    while ((l = 2 * i + 1) < n) {
        g = (a[l] > a[i]) ? l : i;
        if (l + 1 < n && a[l + 1] > a[g]) g = l + 1;
        if (g == i) return;
        t = a[i]; a[i] = a[g]; a[g] = t; i = g;
    }
}
void heap_sort(int a[], int n) {
    int i, t;
    for (i = n / 2 - 1; i >= 0; i--) sift(a, i, n);   /* build heap */
    for (i = n - 1; i > 0; i--) {
        t = a[0]; a[0] = a[i]; a[i] = t;              /* move max to end */
        sift(a, 0, i);                                /* repair heap */
    }
}
```

#### Example: sort 25, 57, 48, 37, 12, 92, 86, 33
Build the max-heap:

| Step | Node heapified | Array |
|---|---|---|
| start | – | 25, 57, 48, 37, 12, 92, 86, 33 |
| 1 | a[3] | 25, 57, 48, 37, 12, 92, 86, 33 |
| 2 | a[2] | 25, 57, 92, 37, 12, 48, 86, 33 |
| 3 | a[1] | 25, 57, 92, 37, 12, 48, 86, 33 |
| 4 | a[0] | 92, 57, 86, 37, 12, 48, 25, 33 |

Initial heap: `92, 57, 86, 37, 12, 48, 25, 33`

```text
level 0:  92
level 1:  57   86
level 2:  37   12   48   25
level 3:  33
```
Sorting phase:

| Pass | Max moved to end | Heap part after re-heapify | Sorted part |
|---|---|---|---|
| 1 | 92 (last position 8) | 86, 57, 48, 37, 12, 33, 25 | 92 |
| 2 | 86 (last position 7) | 57, 37, 48, 25, 12, 33 | 86, 92 |
| 3 | 57 (last position 6) | 48, 37, 33, 25, 12 | 57, 86, 92 |
| 4 | 48 (last position 5) | 37, 25, 33, 12 | 48, 57, 86, 92 |
| 5 | 37 (last position 4) | 33, 25, 12 | 37, 48, 57, 86, 92 |
| 6 | 33 (last position 3) | 25, 12 | 33, 37, 48, 57, 86, 92 |
| 7 | 25 (last position 2) | 12 | 25, 33, 37, 48, 57, 86, 92 |
| – | – | (empty) | 12, 25, 33, 37, 48, 57, 86, 92 |

**Sorted output: 12, 25, 33, 37, 48, 57, 86, 92**

Complexity: O(n log n) in best, average and worst case; O(1) extra space; not stable.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What mainly distinguishes external sorting from internal sorting?
   A. External sorting is always faster
   B. Data is too large for main memory and kept on disk or tape, so cost is dominated by I/O
   C. External sorting uses only comparisons
   D. Internal sorting needs a disk
   Answer: B. External sorting handles data that does not fit in RAM and is read in blocks. (Key point: Internal vs external)

2. In the max-heap used by heap sort, which condition holds?
   A. Every parent is smaller than its children
   B. Every parent is greater than or equal to its children
   C. The array is fully sorted
   D. Left child is always larger than the right
   Answer: B. The root of a max-heap is the largest element. (Key point: Heap property)

3. What is done repeatedly after building the heap?
   A. Swap the root with the last heap element, shrink the heap, and sift the new root down
   B. Insert new keys at the root
   C. Remove the smallest leaf
   D. Rebuild the heap from scratch each time
   Answer: A. The largest goes to its final place at the end, then the heap is repaired. (Key point: Sorting phase)

4. Which describes heap sort?
   A. O(n log n) in all cases, O(1) extra space, not stable
   B. O(n) best case, stable
   C. O(n^2) worst case, stable
   D. O(n log n) with O(n) space, stable
   Answer: A. Heap sort is in-place and unstable with O(n log n) for best, average and worst. (Key point: Properties)

## Related in Data Structure and Algorithm

- [Stable vs unstable sorting; heap](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astable-unstable-heap) — Data Structure and Algorithm, chapter 7
- [Heap sort on 37, 33, 26, 92, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-construct-12-element) — Data Structure and Algorithm, chapter 7
- [Heap tree insertion and heap sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-insertion-and-sort) — Data Structure and Algorithm, chapter 7
- [Algorithm for an exchange sort](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aexchange-sort-algorithm) — Data Structure and Algorithm, chapter 7, asked 2×
- [Merge and radix sort on 142, 523, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amerge-radix-trace-142) — Data Structure and Algorithm, chapter 7
- [Radix sort on 25, 57, 48, 37, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aradix-sort-25-57-48) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Internal/external risks; Nepal; hydropower](https://www.bctengineer.com/question.md?key=semester_7%2Fproject_engineering%3Arisk-internal-external-nepal-hydropower) — Project Engineering, chapter 5
- [Page size impact; internal, external fragmentation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-size-impact-fragmentation) — Operating System, chapter 4
- [Noise, distortion, interference; internal and external noise](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Anoise-types-internal-external) — Communication Systems, chapter 1
- [External vs internal noise; interference sources; need for modulation](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Aexternal-internal-noise-interference-needs) — Communication Systems, chapter 1