What is stable sorting algorithm in data structures

What is stable sorting algorithm in data structures

What is stable sorting algorithm?

A sorting algorithm is said to be stable if two or more elements with equal keys (values) appear in the same order in sorted output as they appear in the unsorted input array.

Sorting stability means that records with the same key retain their relative order before and after the sort.

Example:

Consider the following list of keys which is unsorted.

Index Values/Keys

0 chair

1 table

2 computer

3 keyboard

4 pen

Let us assume that we sort the given array using the key’s (value’s) first letter in ascending alphabetical order. Then the result would be as follows;

Index Values/Keys

0 chair

1 computer

2 keyboard

3 pen

4 table

Here, you can see that the first letter of the keys chair and computer are same. In the unsorted input the key chair comes before computer. Also, after sorting, chair comes before computer. Though they are sorted, their order of appearance has not changed. So the sorting algorithm is said to be a stable algorithm.

List of stable sorting algorithms:

Bubble sort

Insertion sort

Merge sort

Radix sort

List of unstable sorting algorithms

Quick sort

Heap sort

Selection sort

Shell sort

***********

Go to sorting algorithms comparison page

Go to sorting algorithms - time complexity page

What is comparison sort?

What is In-place sort?

stable sorting in data structures

example for stable sorting algorithm

stable vs non-stable algorithms

when do we need stable sort algorithms

how to find stable sort algorithm

list of stable and not-stable sorting algorithms