Stable sorting algorithm
A sorting algorithm is called stable if it preserves the order of elements with the same sorting key. Otherwise it is called unstable. Merge sort is an example of a stable sorting algorithm, quicksort is an example of an unstable sorting algorithm. Note that being stable has nothing to do with how difficult it is to do the sorting (known as complexity). Bubble sort is very easy to implement, but takes a very long time. It is a stable sorting algorithm. Heapsort is very efficient, but it is not stable.
Formally stability may be defined as, how the algorithm treats equal elements. Let A[] be an array, and let ‘<‘ be a strict weak ordering on the elements of A[]. A sorting algorithm is stable if: i < j and A[i]=A[j] implies pi(i) < pi(j) where pi is the sorting permutation (sorting moves A[i] to position pi(i)).
Which sorting algorithms are stable?
Some Sorting Algorithms are stable by nature, such as Bubble Sort, Insertion Sort, Merge Sort, Count Sort, etc.
Which sorting algorithms are unstable?
Quick Sort, Heap Sort etc., can be made stable by also taking the position of the elements into consideration. This change may be done in a way that does not compromise a lot on the performance and takes some extra space.
Stable Sorting Algorithm Media
Sorting a random list using merge sort.
An example of stable sort on playing cards. When the cards are sorted by rank with a stable sort, the two 5s must remain in the same order in the sorted output that they were originally in. When they are sorted with a non-stable sort, the 5s may end up in the opposite order in the sorted output.
Sorting playing cards using stable sort
A Shellsort, different from bubble sort in that it moves elements to numerous swapping positions.
A bubble sort, a sorting algorithm that continuously steps through a list, swapping items until they appear in the correct order.
