The “Fairness” of Sorting: What is Stability? Taking Insertion Sort as an Example¶

Imagine this scenario: you and your deskmate finish a race simultaneously with identical results. The coach says to award prizes based on the “first-come, first-served” rule. Then, your prize order should match your starting order—you started first, so you get the earlier position, and your deskmate, who started later, gets the later position. This is like when people in a queue look identical; everyone defaults to the order of arrival, which is a form of “fairness.”

In computer sorting algorithms, there’s also this kind of “fairness,” and its name is stability.

What is Sorting “Stability”?¶

In simple terms, stability refers to: When two elements with equal values appear in the sorted array, whether their relative order before sorting is preserved. If preserved, the sorting algorithm is stable; if not, it is unstable.

For example, consider the array [3, 1, 3, 2], which contains two equal elements 3 (the first 3 is at index 0, the second at index 2). If after sorting, these two 3s remain in the order “first 3 before the second 3,” the algorithm is stable.

How Does Insertion Sort Demonstrate “Stability”?¶

Let’s use insertion sort to see how it maintains stability. The core idea of insertion sort is: Take one element from the unsorted part and insert it into the correct position in the sorted part.

Simulating the Insertion Sort Process¶

Take the array [3, 1, 3, 2] with two equal 3s. Let’s simulate insertion sort step by step:

1. Initial state: Sorted part is empty; unsorted part is [3, 1, 3, 2].
2. Process the first element 3: Sorted part becomes [3]; unsorted part becomes [1, 3, 2].
3. Process the second element 1: 1 is smaller than 3, so insert before 3. Sorted part becomes [1, 3]; unsorted part becomes [3, 2].
4. Process the third element 3: Current sorted part is [1, 3], and the element to process is 3. Here’s where insertion sort’s “key” comes in:
   - Compare 3 with the last element of the sorted part (3). They are equal. At this point, the insertion sort rule is: Do not swap when equal; directly insert the new element after the equal elements.
   - Thus, 3 is inserted at the end of the sorted part. Sorted part becomes [1, 3, 3]; unsorted part becomes [2].
5. Process the fourth element 2: 2 is smaller than 3, insert before 3. Then compare with 1, and 2 is larger, so insert after 1. The final sorted part is [1, 2, 3, 3].

The final result is [1, 2, 3, 3]. The relative positions of the original two 3s (first at index 0, second at index 2) are preserved: the first 3 comes before the second 3.

Why is Insertion Sort Stable?¶

Insertion sort’s “stability” comes from its insertion logic: When inserting a new element, it starts from the end of the sorted part and compares with elements one by one. It stops moving when it encounters an equal element and directly inserts the new element after it. This ensures: If two elements are equal, the later-occurring element will never come before the earlier-occurring one.

Let’s test with another example: [2, 2, 1]:
- Initial sorted part: [2]. When processing the second 2, since 2 equals the last element of the sorted part, insert it directly after. Sorted part becomes [2, 2].
- Then process 1, insert at the front. The final result is [1, 2, 2]. The relative order of the original two 2s (earlier one first, later one second) is fully preserved.

The Significance of Stability¶

Why care about stability? Imagine ranking students by scores: if two students have the same score, they are ranked by student ID in ascending order. If the sort is unstable, the order of student IDs for equal scores might be disrupted, leading to incorrect rankings for students with smaller IDs. Stability ensures “fairness”—original order is respected when conditions are equal.

Insertion sort excels with duplicate elements due to this “fairness.” For example, sorting e-commerce orders by “amount + time”: orders with the same amount are processed by order time. Stability ensures customers who placed orders earlier are prioritized.

Summary¶

The “fairness” of sorting is stability: Whether the relative order of two equal elements remains unchanged before and after sorting. Insertion sort naturally ensures stability through the insertion logic of “not swapping when equal, inserting directly after.” It’s like lining up for “tied contestants”—strictly respecting the original order, ensuring every element is treated “fairly.”

Next time you see a sorting algorithm, consider: If two identical numbers exist, will their “positions” be swapped? If not, the algorithm is likely stable. And insertion sort is a “fair” sorting algorithm that always respects order.