Question

Which of the following sorting algorithms is stable?

• A. Quick Sort
• B. Merge Sort
• C. Heap Sort
• D. Selection Sort

Hint:

To understand stability:
- A stable sort keeps equal elements in original order.
- Merge Sort is stable; Quick Sort and Heap Sort are not.
- Test with arrays having duplicate keys to observe behavior.

Answer 1

The Correct Option is B

To determine which sorting algorithm is stable, we need to understand the concept of stability in sorting and evaluate each option.
Step 1: Understand Stability in Sorting
A sorting algorithm is stable if it preserves the relative order of equal elements in the sorted output, i.e., if two elements have equal keys, their original order is maintained.
Step 2: Analyze Option A - Quick Sort
Quick Sort uses a pivot and partitioning, which can swap equal elements, potentially changing their relative order.
It is generally not stable unless modified (e.g., with extra space or indexing).
Thus, option A is incorrect.
Step 3: Analyze Option B - Merge Sort
Merge Sort divides the array into halves, sorts them, and merges them while preserving the order of equal elements during the merge process.
When implemented correctly (e.g., stable merge), it maintains the relative order of equal elements.
Thus, option B is correct.
Step 4: Analyze Option C - Heap Sort
Heap Sort builds a heap and repeatedly extracts the maximum element, which can reorder equal elements due to the heap structure.
It is not stable by default.
Thus, option C is incorrect.
Step 5: Analyze Option D - Selection Sort
Selection Sort finds the minimum element and places it at the beginning, which may swap equal elements and change their original order.
It is not stable.
Thus, option D is incorrect.
Step 6: Conclusion
Among the given options, only Merge Sort is inherently stable when implemented with a stable merge procedure, making option B the answer.