What is Stable sorting algorithm?
[[File:Sorting_stability_playing_cards.svg|thumb|Stability when sorting playing cards]] 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 [[Big O notation|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|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. {{math-stub}} [[Category:Searching and sorting algorithms]]