Stable Sorting
Keeping ties in order.
When two items are equal, a stable sort keeps them in the same order they started in. That sounds like a small detail, but it lets you sort by several things, one step at a time.

- Equal items keep their order
- A small detail
- Sort in steps
Sorting in two steps
Here are students, already in alphabetical order. Now we sort them by grade. Python's sort is stable, so students with the same grade stay in alphabetical order. Run it. Alex and Mia both got an A, and Alex is still before Mia.
students = [("Alex", "A"), ("Ben", "B"), ("Jo", "C"),
("Mia", "A"), ("Sam", "B"), ("Zoe", "C")]
by_grade = sorted(students, key=lambda s: s[1])
for name, grade in by_grade:
print(grade, name)A Alex A Mia B Ben B Sam C Jo C Zoe
Which sorts are stable?
Here's a summary of the sorts we've met. Bubble, insertion, and merge sort are stable. Selection sort and the usual quick sort are not. Python's built in sort, called Timsort, is stable, and runs in O of N log N. It mixes merge sort and insertion sort.
| Sort | Time | Stable? |
|---|---|---|
| Bubble | O(n²) | yes |
| Selection | O(n²) | no |
| Insertion | O(n²) | yes |
| Merge | O(n log n) | yes |
| Quick | O(n log n) avg | no |
| Python sorted() | O(n log n) | yes |
Summary
A stable sort keeps equal items in their original order, so you can sort in steps. Python's sort is stable. Next, a sort that doesn't compare at all.
Key takeaways- Ties keep their order
- Python's sort is stable
- Sort in steps