GATE CS 1999 Q1.12 — Searching, Sorting, Hashing

A sorting algorithm is defined as stable if it preserves the relative order of equal (non-distinct) elements in the sorted output as they appeared in the original input.

Formally, if two items $A_i$ and $A_j$ have the same key value (i.e., $key(A_i) = key(A_j)$) and $A_i$ appears before $A_j$ in the input list, then $A_i$ will also appear before $A_j$ in the sorted list.

• Option A: Stability is independent of time complexity. For example, Merge Sort is stable and takes $O(n \log n)$ time, while Heap Sort is unstable but also takes $O(n \log n)$ time.
• Option B: This is the exact definition of stability.
• Option C: Stability is independent of the design paradigm. Merge Sort (divide-and-conquer) is stable, whereas Quick Sort (also divide-and-conquer) is typically unstable.
• Option D: Stability is independent of space complexity.

Therefore, the correct option is B.