When we talk about sorting algorithms, it’s important to know about stability.

A stable sorting algorithm keeps the order of items that are the same, while an unstable sorting algorithm does not.

So, how do we figure out if an algorithm is stable or unstable?

What is Stability?

1. Definition: A sorting algorithm is stable if it keeps the order of items that are equal. For example, if you have two identical items, let's say 'A' and 'B', and 'A' is listed before 'B' in the original list, a stable algorithm will keep 'A' before 'B' in the sorted list too.

2. Examples of Stable Algorithms:

   • Bubble Sort: This algorithm looks at pairs of items next to each other and swaps them if needed. It makes sure equal items stay in the same order.
   • Merge Sort: It splits the list into smaller parts, sorts those parts, and then puts them back together while keeping the order of equal items.

3. Examples of Unstable Algorithms:

   • Quick Sort: Depending on how it picks its main item (called a pivot), equal items can end up in different places, which makes it unstable.
   • Heap Sort: The way it builds a heap can change the original order of equal items.

In short, to figure out if a sorting algorithm is stable or unstable, think about how it deals with items that are the same. If their order stays the same, then the algorithm is stable. If not, it is unstable.