The built-in sort is a tuned hybrid, not a textbook algorithm. It exploits runs already in the data, which is why sorting real data is faster than the worst case suggests.
About 2 min of reading
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Use the built-in sort.
Sort a row with a run.
Before you run it, say out loud what it will print. Then open the answer.
Sort in place.
Before you run it, say out loud what it will print. Then open the answer.
Sort words by length.
Before you run it, say out loud what it will print. Then open the answer.
Sort descending.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
Timsort merges sorted runs it finds and uses insertion sort for short ones. Real data has runs, so it beats the worst case often.
A hand-written quicksort or merge sort is for learning. Production code calls the built-in sort, which is tuned and stable.
nums = [1, 2, 3, 0, 9, 8]
print(sorted(nums))The sort spots that 1,2,3 is already ordered and 9,8 is a reversed run. It uses those instead of starting over.
nums = list(range(100))
nums[50], nums[51] = nums[51], nums[50]
print(nums == sorted(nums))One swap out of place. The built-in sort fixes it cheaply because it works on runs.
rows = [(2, "a"), (2, "b")]
print(sorted(rows))The built-in sort is stable. Ties keep input order, which the multi-field trick needs.
nums = [3, 1, 2]
nums.sort()
print(nums)list.sort changes the list and returns nothing. sorted returns a new list. Same algorithm, two shapes.
words = ["owlww", "ox", "bee"]
print(sorted(words, key=len))The key runs once per item, then the sort orders the measures. An expensive key is paid once.
nums = [1, 3, 2]
print(sorted(nums, reverse=True))The reverse flag flips the comparison. No second pass is needed.
print(sorted([2, "a"]))Numbers and text cannot be compared. A key that maps both to one type is the fix.
import random
nums = [random.randint(0, 100) for _ in range(50)]
print(sorted(nums) == sorted(nums))Even random data sorts fast. The built-in sort is tuned for the mix of runs real data has.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.