Stable sort preserving equal order demo in Python

Demonstrates Python's stable sort, showing that elements with equal sort keys retain their original relative order.

Easy Python 3.9+ Aug 9, 2026 Algorithms & data structures 13 views 0 copies

sorting stable sort timsort algorithm

Python code

17 lines

Python 3.9+

from operator import itemgetter

def stable_sort_demo():
    data = [(3, "first"), (1, "second"), (3, "third"), (1, "fourth"), (2, "fifth")]
    print("Original:", data)
    
    # Sort by first element (the tuple's first value), keeping relative order of equal items
    sorted_data = sorted(data, key=itemgetter(0))
    print("Stable sorted:", sorted_data)
    
    # Show original indices to prove stability
    indexed = [(i, *item) for i, item in enumerate(data)]
    indexed.sort(key=lambda x: x[1])  # x[1] is the first element of the original tuple
    print("With original indices:", indexed)

if __name__ == "__main__":
    stable_sort_demo()

Output

stdout

Original: [(3, 'first'), (1, 'second'), (3, 'third'), (1, 'fourth'), (2, 'fifth')]
Stable sorted: [(1, 'second'), (1, 'fourth'), (2, 'fifth'), (3, 'first'), (3, 'third')]
With original indices: [(1, 1, 'second'), (3, 1, 'fourth'), (4, 2, 'fifth'), (0, 3, 'first'), (2, 3, 'third')]

How it works

Python's built-in sorted() and list.sort() use Timsort, which is stable. This means elements with equal keys retain their original order. In the example, tuples with the same first value (1 or 3) appear in the same relative order as they did in the input. The index-tracking version makes this explicit by sorting tuples that also carry the original position.

Common mistakes

Assuming `sorted` is unstable like quicksort and writing extra code to handle ties
Forgetting that stability only applies to equal keys, not all elements
Using a key function that returns a non-sortable object (e.g., mixing types)
Not realizing that `sort()` modifies in-place while `sorted()` returns a new list

Variations

Use `list.sort()` instead of `sorted()` when you want to sort in place
Use `enumerate` and a key that includes both values to implement a more complex stable ordering

Real-world use cases

Sorting logs by timestamp while preserving the order of events that happen at the same time.
Rearranging database rows by a secondary column without breaking the primary ordering from a previous sort.
Stably grouping user actions by priority while keeping the sequence they occurred in.

Stable sort preserving equal order demo in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes