Stable Sorting

Stable Sorting

Stable sorting refers to a sorting algorithm’s ability to preserve the relative order of equal elements in the sorted output. In other words, if two elements have the same value (or key), a stable sorting algorithm ensures they appear in the same order in the sorted result as they did in the original input.

Example

Suppose you have a list of objects with names and ages:

• Input: [(Alice, 25), (Bob, 30), (Charlie, 25)]
• Sorting by age.

Stable Sorting:

• Output: [(Alice, 25), (Charlie, 25), (Bob, 30)]
• Alice and Charlie, both aged 25, maintain their original order (Alice before Charlie).

Unstable Sorting:

• Output might be: [(Charlie, 25), (Alice, 25), (Bob, 30)]
• The order of Alice and Charlie (equal age) could be swapped.

Why Stability Matters

• Multi-key sorting: When sorting by multiple criteria (e.g., first by age, then by name), stability ensures that earlier sorts are preserved. For example, sorting by name after sorting by age keeps equal ages in name-sorted order.
• Data integrity: In applications where the relative order of equal elements carries meaning (e.g., database records), stability prevents unintended reordering.

Stable vs. Unstable Algorithms

• Stable: Merge Sort, Insertion Sort, Bubble Sort
• Unstable: Quick Sort, Heap Sort, Selection Sort

If you need a specific example or a visual to clarify, let me know!