Last reviewed
Correct answer: B. Elements with equal values retain their relative original order after sorting
Explanation
Stability is a promise about ties, and only about ties. When two records compare equal on the sort key, a stable sort leaves them in the order they arrived; an unstable one is free to swap them. NIST states the definition in exactly those terms, and Python guarantees it for sorted and list.sort.
The payoff shows up when one sort is not enough. To list students by descending grade and, within each grade, by ascending age, sort on age first and then sort on grade. The second pass only moves records whose grades differ, so the age ordering survives inside every grade group. That two-pass idiom is the reason the guarantee is worth writing down. Radix sort leans on the same property: each digit pass must be stable or the earlier passes are undone.
The other options describe things stability is not. A sort making no comparisons would say nothing about how ties are ordered. Constant running time is a complexity claim, unreachable for a comparison sort, and unrelated to ordering. Nothing about stability caps how many elements a sort accepts.
Sources
“Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.”
“An algorithm where the relative order upon input of items with equal keys is always preserved in the output.”
“This is what a stable sorting algorithm guarantees.”
Practise 3 questions on this topic
Take Sorting & Searching — Timed Test (3 questions) — scored instantly, explanation for every question, no login.