Stable and unstable sorting
In the following paragraphs, we will discuss stable and unstable sorting.
Stable sorting
A stable sort algorithm maintains the relative ordering of elements of equal values in a sorted sequence. It can be understood using the following diagram:
As the diagram depicts, our unsorted list has two fives. The first 5 is in a white slot and the second one is in a gray slot. After sorting, in the sorted sequence also, the 5 in the white slot remains before the 5 in the gray slot. This is an example of a stable sort.
Unstable sorting
Unstable sorting algorithms do not maintain the relative ordering of elements of equal values in a sorted sequence. The following diagram will help in understanding unstable sorting:
As shown in the figure, in a sorted sequence, the 5 in gray slot is before the 5 in white slot. In the unsorted sequence, the 5 in white slot is before the 5 in gray slot. After sorting, in the sorted sequence, their relative ordering is changed. This is...
