Unstable Sort
Table of Contents
What is an Unstable Sort? #
An unstable sort is a sorting algorithm that does not preserve the relative order of equal elements in the input list. This means that if two elements are equal in the input list, their relative order may not be preserved in the sorted list.
An unstable sort may change the order of equal elements in the input list.
In simpler terms, if you have a list where some elements are equal, an unstable sorting algorithm may rearrange these equal elements in a different order than they appeared in the original list.
Unstable Sort Vs Stable Sort #
For example, consider a list of items with a name and a number, and you’re sorting them by number:
- (Apple, 1)
- (Banana, 2)
- (Cherry, 2)
- (Date, 1)
After an unstable sort by the numbers, it’s possible to end up with:
- (Date, 1)
- (Apple, 1)
- (Cherry, 2)
- (Banana, 2)
Notice that even though Apple and Date both have the number 1, Date comes before Apple in the sorted list, which is different from their original order. The same goes for Banana and Cherry. This characteristic is what defines an unstable sort.
In contrast, a stable sort would maintain the original relative order of records with equal keys (in this case, numbers). So, after a stable sort, the items with equal numbers would appear in the same order as they did before the sort:
- (Apple, 1)
- (Date, 1)
- (Banana, 2)
- (Cherry, 2)
Stability of Sorting Algorithms #
The table below categorizes some common sorting algorithms by their stability, distinguishing between stable and unstable algorithms.
| Sorting Algorithm | Stability |
|---|---|
| QuickSort | Unstable |
| HeapSort | Unstable |
| MergeSort | Stable |
| Insertion Sort | Stable |
| Bubble Sort | Stable |
The choice between using a stable or unstable sorting algorithm depends on the requirements of the application and the specific characteristics of the data being sorted.