Python Timsort: Stable Sorting with sorted() and sort()

Quick answer: Python’s sorted and list.sort use Timsort, a stable adaptive sorting algorithm. Give them a key function that expresses the domain order, choose mutation versus a new list deliberately, and use stability when a secondary order must be preserved.

Python TimSort is the sorting algorithm behind the built-in sorted() function and list.sort() method. It is stable, adaptive, and designed to perform well on real-world data that often already contains ordered runs.

For normal Python programs, you should use sorted() or list.sort() instead of writing TimSort yourself. The point of learning TimSort is to understand why Python sorting is stable, why key functions are powerful, and why partially sorted data can be handled efficiently.

TimSort was designed for practical data, not only random benchmark arrays. Logs, reports, imported CSV files, and user-facing tables often arrive with sections that are already ordered. TimSort can use those runs instead of ignoring them.

What Is TimSort?

TimSort is a hybrid sorting algorithm based on merge sort and insertion sort ideas. It looks for existing sorted sections, called runs, extends or sorts small runs, and then merges runs while preserving order. Python’s sorting HOWTO highlights stability and key functions as core parts of Python sorting.

numbers = [5, 2, 9, 1, 5, 6]

print(sorted(numbers))

numbers.sort()
print(numbers)

sorted() returns a new list. list.sort() sorts the original list in place and returns None. Both use Python’s built-in sorting machinery.

Stability in Python Sorting

A stable sort preserves the original relative order of items that compare equal. This is important when sorting records in multiple passes or when values have a meaningful original order.

students = [
    ("Maya", "B", 92),
    ("Ravi", "A", 91),
    ("Nina", "B", 88),
    ("Omar", "A", 85),
]

by_grade = sorted(students, key=lambda row: row[1])
print(by_grade)

The two A records stay in their original order relative to each other, and the two B records do the same. This behavior makes stable sorting useful for tables, reports, and grouped data. It also lets you sort by a secondary field first, then by a primary field later.

Use key Functions Instead of Custom Sorting Code

Most custom sorting needs can be solved with a key function. A key function extracts the value Python should sort by, while TimSort handles the actual ordering efficiently.

records = [
    {"name": "api", "latency": 120},
    {"name": "worker", "latency": 85},
    {"name": "db", "latency": 210},
]

fastest_first = sorted(records, key=lambda item: item["latency"])
print(fastest_first)

For tuple-specific examples, see sort a list of tuples in Python. Key functions are usually clearer than reimplementing a sorting algorithm. They also keep the sort rule close to the call site, which makes later maintenance easier.

Natural Runs and Adaptive Behavior

TimSort is adaptive because it can take advantage of existing order. Real data often arrives in sorted or nearly sorted chunks: timestamps, logs, ranking updates, and paginated exports are common examples.

data = [1, 2, 3, 8, 9, 4, 5, 6]

# Python's built-in sort can exploit ordered runs internally.
print(sorted(data))

You do not need to manually detect runs when using Python. The built-in sort handles that internally. The practical lesson is that Python sorting is already optimized for many real inputs, not only random lists. If the data is already almost sorted, Python can often finish with less work than a simple comparison-sort demonstration would suggest.

Complexity of Python TimSort

Python sorting has O(n log n) worst-case time complexity. It can be closer to linear time on data that already has long ordered runs. The sort is stable and uses additional memory during merging.

words = ["pear", "fig", "banana", "kiwi", "apple"]

by_length = sorted(words, key=len)
print(by_length)

When memory or performance matters, benchmark the actual workload. In nearly all application code, built-in sorting is the right baseline before considering a specialized algorithm. It is implemented in optimized Python internals and has been tested across far more cases than a short tutorial implementation.

When Should You Implement TimSort Yourself?

Almost never for production Python code. Implementing TimSort correctly is complex because it manages run sizes, merge invariants, and edge cases. For learning, it is fine to study simplified merge and insertion sort pieces, but use the built-in sort for real data.

items = [("b", 2), ("a", 3), ("b", 1)]

items.sort(key=lambda item: item[0])
print(items)

Common Sorting Mistakes

Remember that list.sort() changes the list in place and returns None. Use sorted() when you need a new list. Also check indexes carefully when experimenting with manual sorting code; the list index out of range guide covers common mistakes.

numbers = [3, 1, 2]
result = numbers.sort()

print(numbers)
print(result)

The sorted values are in numbers, while result is None. This is expected behavior for in-place list methods. If you need both the old and new order, copy the list first or use sorted().

Conclusion

Python TimSort is the stable, adaptive sorting algorithm used by sorted() and list.sort(). It works well on real-world data because it can exploit existing sorted runs while still providing reliable worst-case performance. In practice, focus on choosing good key functions and the right API, not on reimplementing TimSort by hand.

Use A Key Function

A key function extracts the value to compare and is usually clearer than repeatedly comparing whole records. Normalize values at the boundary when the order requires it, and keep the key deterministic for the duration of a sort.

Rely On Stability

Equal keys keep their original relative order. This enables a secondary sort followed by a primary sort, or a single tuple key when both rules should be visible together. Stable behavior is especially useful for records arriving in a meaningful source order.

Choose sorted Or sort

sorted returns a new list and accepts any iterable, while list.sort mutates a list and returns None. Use sorted when the original data must remain available; use sort when mutation is intentional and reducing an extra list matters.

Make Ties Predictable

Define case, missing-value, and type policies before sorting. Mixed incomparable types or a key that changes during execution can make a valid algorithm fail. Test equal keys, empty input, reverse order, and already ordered data.

Think About The Data Contract

Timsort can exploit existing runs, but it still needs a complete comparison policy. Document what ascending means, how null values are placed, and which fields break ties so future callers do not infer a different business order.

Python’s Sorting HOW TO documents key functions and stability, and sorted() defines the built-in contract. Related references include itemgetter, rich comparisons, and grouping sorted data.

For related ordering workflows, compare itemgetter, rich comparisons, and grouping sorted data when defining a stable order.

Frequently Asked Questions

What sorting algorithm does Python use?

Python’s list.sort and sorted use Timsort, a stable adaptive algorithm designed to perform well on partially ordered data.

What does stable sorting mean?

Records with equal keys keep their original relative order, which enables reliable multi-pass and secondary-key sorting.

Should I use sorted or list.sort?

Use sorted when a new list is needed and list.sort when mutating an existing list is intentional and memory matters.

How do I sort complex records?

Pass a key function such as itemgetter or a lambda that returns the domain’s ordering value.