Which of the following is stable sort
Merge sort
Understanding Stable Sort Algorithms
Sorting algorithms arrange elements in a list based on a specific order. A key property some sorting algorithms have is called stability.
A sorting algorithm is considered stable if it preserves the relative order of equal elements. This means if two elements have the same value, their original order in the unsorted list is maintained in the sorted list.
Let's consider an example to illustrate stability. Suppose we have a list of pairs where the first element is the value and the second is an original index to show their initial positions: [(3, 1), (1, 2), (2, 3), (3, 4)]. If we sort this list based on the value, a stable sort would produce [(1, 2), (2, 3), (3, 1), (3, 4)], where the two elements with value 3 remain in their original order (the one with original index 1 comes before the one with original index 4). An unstable sort might produce [(1, 2), (2, 3), (3, 4), (3, 1)], changing the relative order of the equal elements.
Analyzing the Given Sorting Algorithms
Let's examine the stability property of each sorting algorithm provided in the options:
- Quick Sort: Quick sort is a highly efficient comparison sort algorithm. However, it is generally not stable. Its partitioning process can change the relative order of equal elements.
- Heap Sort: Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. Heap sort is also not stable. Its process of building and extracting from the heap can alter the relative order of equal elements.
- Merge Sort: Merge sort is a divide-and-conquer sorting algorithm. It works by dividing the list into sub-lists, sorting them, and then merging the sorted sub-lists back together. The merging process in merge sort can be implemented in a way that preserves the relative order of equal elements. Therefore, Merge sort is a stable sorting algorithm.
- Selection Sort: Selection sort is a simple comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part and putting it at the beginning. Selection sort is generally not stable. For example, if you have [(5, 1), (5, 2), (2, 3)], the first step finds 2 and swaps it with the first 5, resulting in [(2, 3), (5, 2), (5, 1)], changing the relative order of the two 5s.
Based on the analysis, Merge sort is the stable sorting algorithm among the given options.
| Sorting Algorithm | Stable? |
|---|---|
| Quick Sort | No |
| Heap Sort | No |
| Merge Sort | Yes |
| Selection Sort | No |
Revision Table: Sorting Algorithm Stability
| Algorithm | Average Time Complexity | Worst-Case Time Complexity | Space Complexity | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n2) | O(n2) | O(1) | Yes |
| Insertion Sort | O(n2) | O(n2) | O(1) | Yes |
| Selection Sort | O(n2) | O(n2) | O(1) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n2) | O(log n) to O(n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) or O(n logb k) | O(nk) or O(n logb k) | O(n + k) or O(k) | Yes (depending on implementation) |
Additional Information on Sorting Algorithms
Beyond stability, sorting algorithms can be characterized by other properties:
- Time Complexity: How the execution time grows with the input size (e.g., O(n log n), O(n2)).
- Space Complexity: How much extra memory the algorithm requires (e.g., O(1) for in-place sorts, O(n)).
- In-Place Sorting: An algorithm that sorts the data structure in place, requiring only a small amount of extra memory beyond that needed for the input.
- Comparison Sort: An algorithm that reads the data only through a comparison operator (e.g., < , > , = ). Quick sort, Merge sort, Heap sort, Bubble sort, Insertion sort, and Selection sort are comparison sorts.
- Non-Comparison Sort: Algorithms that do not use comparisons to sort, often relying on properties of the keys (e.g., Counting sort, Radix sort). These can achieve better time complexity than comparison sorts in certain cases but have limitations on the data they can sort.
Understanding these properties helps in choosing the most appropriate sorting algorithm for a given task.
Important Questions from Sorting - Teaching
Arrange the following items in ascending order using Bubble Sort. What is the intermediate sequence of 37, 54, 21, 85, 68, 12, 9, and 57 after the second pass?
Which of the following algorithm design approach is used in Quick sort algorithm?
What is the worst case running time of quick sort algorithm?
Sort the following list using the Radix sort algorithm.
329, 457, 839, 436, 720, 355, 657
What is the output of the algorithm after the second pass?
You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences.
The lower bound on the number of comparisons needed to solve this variant of the sorting problem is :
