Problem Statement
Which of the following sorting algorithms is stable?
Explanation
A stable sorting algorithm maintains the relative order of equal elements. Merge Sort is stable because when merging two sorted arrays, if elements are equal, we always pick from the left array first, preserving the original order.
Quick Sort and Heap Sort are not stable because they can change the relative order of equal elements during partitioning or heap operations. Selection Sort is also not stable because it swaps elements without considering equal elements. Stability is important when sorting objects by multiple keys or when the original order of equal elements matters.
Code Solution
SolutionRead Only
// Stability example:
// Input: [(3,a), (1,b), (3,c), (2,d)]
// Sort by first element
// Stable sort (Merge Sort):
// Output: [(1,b), (2,d), (3,a), (3,c)]
// Note: (3,a) comes before (3,c) - order preserved
// Unstable sort (Quick Sort):
// Output: [(1,b), (2,d), (3,c), (3,a)]
// Note: (3,c) comes before (3,a) - order changed
// Why Merge Sort is stable:
void merge(int[] arr, int left, int mid, int right) {
// When arr[i] == arr[j]
// Always pick from left subarray first
if (arr[i] <= arr[j]) { // <= ensures stability
temp[k++] = arr[i++];
}
}