--- title: "Stable vs unstable sorting; heap" subject: "Data Structure and Algorithm" chapter: 7 key: "semester_4/data_structure_and_algorithm:stable-unstable-heap" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/stable-unstable-heap site: BCT Engineering --- # Stable vs unstable sorting; heap Data Structure and Algorithm · Chapter 7: Sorting - Asked in: 2070 Magh, 2+4+2 marks - Video: [Stable Vs Unstable Sort [FULL]](https://www.youtube.com/watch?v=X1DUh3JhLTw) — Techdose - 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/stable-unstable-heap - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-7 ## Question Differentiate between stable and unstable sorting with example. Construct a heap for the following data: 8, 10, 5, 12, 14, 18, 19. What is the time complexity for sorting the unsorted elements using heap-sort? ## Short answer Stable sorting preserves original relative order of equal keys (e.g., bubble sort); unstable does not (e.g., heap sort). Building a max-heap for 8,10,5,12,14,18,19 by insertion yields array 19,12,18,8,10,5,14. Heap sort complexity is O(n log n) in all cases. ## Answer #### Stable and unstable sorting A sorting algorithm is **stable** if records with equal keys stay in the same relative order after sorting. An **unstable** algorithm may change that order. Example: sort by marks the records (Ram, 80), (Sita, 90), (Hari, 80). - Stable result: (Ram, 80), (Hari, 80), (Sita, 90). Ram is still before Hari. - Unstable result: (Hari, 80), (Ram, 80), (Sita, 90). Their order has changed. | Stable | Unstable | |---|---| | Bubble, insertion, merge, counting, radix sort | Selection, quick, heap, shell sort | | Needed when sorting on multiple keys in succession | Equal keys may be reordered | #### Heap for 8, 10, 5, 12, 14, 18, 19 (max-heap by successive insertion) | Step | Insert | Array (heap) after step | Moves | |---|---|---|---| | 1 | 8 | 8 | none | | 2 | 10 | 10, 8 | 10↔8 | | 3 | 5 | 10, 8, 5 | none | | 4 | 12 | 12, 10, 5, 8 | 12↔8, 12↔10 | | 5 | 14 | 14, 12, 5, 8, 10 | 14↔10, 14↔12 | | 6 | 18 | 18, 12, 14, 8, 10, 5 | 18↔5, 18↔14 | | 7 | 19 | 19, 12, 18, 8, 10, 5, 14 | 19↔14, 19↔18 | ```text 19 / \ 12 18 / \ / \ 8 10 5 14 ``` Array form: 19, 12, 18, 8, 10, 5, 14. Every parent is greater than or equal to its children. (A min-heap built the same way would be 5, 10, 8, 12, 14, 18, 19.) #### Time complexity of heap sort Building the heap takes O(n); each of the n − 1 extractions needs a sift-down of O(log n). So the time for sorting is **O(n log n)** in the best, average and worst cases (space O(1)). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What makes a sorting algorithm stable? A. It sorts in O(n log n) B. Records with equal keys keep their original relative order C. It uses no extra space D. It works only on sorted data Answer: B. Stability keeps equal keys in input order. (Key point: Stable definition) 2. Which group contains only stable sorts? A. Bubble, insertion, merge B. Selection, quick, heap C. Heap, shell, merge D. Quick, bubble, selection Answer: A. Bubble, insertion, merge, counting and radix are stable; selection, quick, heap and shell are not. (Key point: Examples) 3. In the max-heap built from 8, 10, 5, 12, 14, 18, 19, which key is the root? A. 8 B. 14 C. 18 D. 19 Answer: D. 19 is the largest and moves up to the root. (Key point: Heap root) 4. What is the time complexity of heap sort? A. O(n^2) worst case B. O(n log n) in best, average and worst cases C. O(n) best case D. O(log n) Answer: B. Build is O(n) plus n-1 sift-downs of O(log n). (Key point: Heap sort time) ## Related in Data Structure and Algorithm - [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 - [Heap sort with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aheap-sort-example) — 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 - [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 ## Related in other subjects - [Stable/unstable systems; test stability](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Astability-define-test-72c) — Data Communication, chapter 2 - [K-map Σ(1,2,3,8,9,10,11,14)+d(0,4,12), NAND](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Akmap-nand-1238-dc-0412) — Digital Logic, chapter 3, asked 5× - [Class C pool for 10, 12, 8, 14](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Asubnetting-class-c-four-depts) — Computer Networks and Security, chapter 4, asked 2× - [Σ(0,1,3,6,10,12,14) using 8×1 MUX](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Amux-8x1-function-0136) — Digital Logic, chapter 4