Skip to main content

Stable vs unstable sorting; heap

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.

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?

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.
StableUnstable
Bubble, insertion, merge, counting, radix sortSelection, quick, heap, shell sort
Needed when sorting on multiple keys in successionEqual keys may be reordered

Heap for 8, 10, 5, 12, 14, 18, 19 (max-heap by successive insertion)

StepInsertArray (heap) after stepMoves
188none
21010, 810↔8
3510, 8, 5none
41212, 10, 5, 812↔8, 12↔10
51414, 12, 5, 8, 1014↔10, 14↔12
61818, 12, 14, 8, 10, 518↔5, 18↔14
71919, 12, 18, 8, 10, 5, 1419↔14, 19↔18
          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)).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →