Past exam question: 2078 Poush (Back), Q4
Open in the Padhaiko appQuestion
Why do you need external sorting? Sort the following elements using max heap and also analyse its computational complexity. 42, 36, 56, 27, 63, 72, 62, 15
Solution
Need for External Sorting: External sorting is required when the dataset to be sorted is too large to fit inside main memory (RAM) and must reside on secondary storage (HDD/SSD). Because disk I/O is orders of magnitude slower than RAM, external sorting (such as external -way merge sort) splits data into memory-sized sorted runs and merges them sequentially to minimize disk block transfers.
Building the Max-Heap from [42, 36, 56, 27, 63, 72, 62, 15]: Last non-leaf index is :
- Heapify index
3(27, child15):27 >= 15, no swap. - Heapify index
2(56, children72, 62): swap56with72[42, 36, 72, 27, 63, 56, 62, 15]. - Heapify index
1(36, children27, 63): swap36with63[42, 63, 72, 27, 36, 56, 62, 15]. - Heapify index
0(42, children63, 72): swap42with72, then42with62Max-Heap:[72, 63, 62, 27, 36, 56, 42, 15].
Extraction and Heapify-Down Passes:
- Swap root
72with15, heapify size 7[63, 36, 62, 27, 15, 56, 42 | 72]. - Swap root
63with42, heapify size 6[62, 36, 56, 27, 15, 42 | 63, 72]. - Swap root
62with42, heapify size 5[56, 36, 42, 27, 15 | 62, 63, 72]. - Swap root
56with15, heapify size 4[42, 36, 15, 27 | 56, 62, 63, 72]. - Swap root
42with27, heapify size 3[36, 27, 15 | 42, 56, 62, 63, 72]. - Swap root
36with15, heapify size 2[27, 15 | 36, 42, 56, 62, 63, 72]. - Swap root
27with15, size 1[15, 27, 36, 42, 56, 62, 63, 72].
Computational Complexity of Heap Sort:
- Build Max-Heap: Takes time (bottom-up heapification).
- Extract Max ( times): Each extraction swaps root and restores heap in time .
- Time Complexity: Best, Average, and Worst cases are all .
- Space Complexity: auxiliary space (in-place sorting).
Answer:
- External Sorting: Needed when data exceeds RAM capacity so sorting minimizes slow disk I/O via run generation and multi-way merging.
- Sorted Output:
15, 27, 36, 42, 56, 62, 63, 72. - Complexity: time (all cases), auxiliary space.