If you need a sort that gives a Θ(n log n) worst-case guarantee AND preserves the order of equal-keyed elements, pick
Aquick sort (in-place and fast in practice)
Bcounting sort (O(n + r))
Cradix sort (O(n × k))
Dmerge sort (Θ(n log n) + stable)
Answer & Solution
Correct answer: D. merge sort (Θ(n log n) + stable)
Merge sort is the only one of these with BOTH a Θ(n log n) worst-case guarantee and stability. Quick sort is fast in practice but has O(n²) worst case and is unstable. Counting and radix have linear time only when keys fit a bounded universe; they are stable but don't give an n log n guarantee on general inputs.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for