Algorithm Design Questions
The difference between a stable and an unstable sorting algorithm lies in how they handle elements with equal keys during the sorting process.
A stable sorting algorithm maintains the relative order of elements with equal keys. This means that if two elements have the same key, the one that appears first in the original input will also appear first in the sorted output. The stability of a sorting algorithm is important in certain scenarios where the original order of equal elements needs to be preserved.
On the other hand, an unstable sorting algorithm does not guarantee the preservation of the relative order of elements with equal keys. In such algorithms, the order of equal elements in the sorted output may differ from their original order in the input. Unstable sorting algorithms are generally faster and require less memory compared to stable sorting algorithms.
In summary, the main difference between stable and unstable sorting algorithms is the preservation of the relative order of elements with equal keys.