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

Stable sorting algorithm
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 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.


Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.