AI Hints
Home›DSA in Python Tutorial›Quick Sort and Keys
DSA in Python · Lesson 57 of 132

Stable Sorting

Keeping ties in order.

⏱ 2 min read▶ Video at 1:06:39🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Stable Sorting
From the video: Stable Sorting
  • 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.

stable.pypython
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)
Output
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.

SortTimeStable?
BubbleO(n²)yes
SelectionO(n²)no
InsertionO(n²)yes
MergeO(n log n)yes
QuickO(n log n) avgno
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
Next up: Counting Sort — sorting without comparing