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.
