A sorting technique is called stable if:
1999
A sorting technique is called stable if:
- A.
It takes O(n log n) time
- B.
It maintains the relative order of occurrence of non-distinct elements
- C.
It uses divide and conquer paradigm
- D.
It takes O(n) space
Attempted by 92 students.
Show answer & explanation
Correct answer: B
A sorting algorithm is stable if equal/non-distinct elements appear in the sorted output in the same relative order in which they appeared in the input.
For example, if two records have the same key and the first one appears before the second one in the original array, a stable sort keeps that order after sorting.
This property is independent of time complexity, the divide-and-conquer paradigm, or auxiliary space usage. Therefore, the correct answer is: it maintains the relative order of occurrence of non-distinct elements.