What is “stability” in sorting algorithms and why is it important?

A stable sorting algorithm is the one that sorts the identical elements in their same order as they appear in the input, whilst unstable sorting may not satisfy the case.

Stable Sorting Algorithms:

• Insertion Sort
• Merge Sort
• Bubble Sort
• Tim Sort
• Counting Sort

Unstable Sorting Algorithms:

• Heap Sort
• Selection sort
• Shell sort
• Quick Sort

So stability matters if, and only if, the problem you’re solving requires retention of that relative order.

• If you don’t need stability, you can use a fast, memory-sipping algorithm from a library, like heapsort or quicksort, and forget about it.
• If you need stability, it’s more complicated. Stable algorithms have higher big-O CPU and/or memory usage than unstable algorithms. So when you have a large data set, you have to pick between beating up the CPU or the memory.