Sorting

Introduction

Python uses Timsort — O(n log n) worst case, O(n) on partially sorted data. sorted() returns a new list; list.sort() mutates.

Understanding the topic

Core concepts to understand:

• sorted(xs) returns a new list.
• xs.sort() mutates in place.
• key= defines sort order.
• reverse=True for descending.

Syntax reference

Visual flow / code:

nums = [3, 1, 4, 1, 5, 9]
sorted(nums)                 # [1,1,3,4,5,9]
sorted(nums, reverse=True)   # [9,5,4,3,1,1]

# Sort by key
words = ["banana", "apple", "cherry"]
sorted(words, key=len)       # by length

# Stable sort by multiple keys
people = [{"age": 30, "name": "B"}, {"age": 30, "name": "A"}]
sorted(people, key=lambda p: (p["age"], p["name"]))

Execution workflow

Real-world use

Timsort is the gold standard — Java 7+ uses it too. The key function is more efficient than cmp (removed in Py3).

Best practices

• Use key over comparison functions.
• Sort is stable — exploit it for multi-level sort.
• sorted for safety; .sort() for memory.

Hands-on exercise

Interview preparation — practice these questions:

• Timsort time complexity?
• Is Python sort stable?
• sorted vs .sort()?

Summary

In summary: Timsort O(n log n), stable. key= is the idiomatic API.