The Self-Taught Computer Scientist

Chapter 4 Sorting Algorithms
53
process until there is only one student left and they’ve added up all of the change in the room. Instead 
of 50 steps, using a merge to count the room’s change takes only 6 steps.
Sorting Algorithms in Python
Python has two built- in sort functions: 
sorted
and 
sort
. Python’s sorting functions use Timsort, a 
hybrid sorting algorithm that combines merge sort and insertion sort. A hybrid sorting algorithm is 
one that combines two or more other algorithms that solve the same problem, either choosing one 
(depending on the data) or switching between them throughout the algorithm. Timsort’s mix of inser-
tion and merge sort makes it an efficient algorithm and is the reason you usually use Python’s built- in 
sorting algorithms instead of trying to code your own.
Python’s 
sorted
function allows you to sort any iterable, as long as Python can compare the data 
in it. For example, you can call 
sorted
on a list of integers, and Python will return a new list with the 
integers from the original list sorted in ascending order:
a_list = [1, 8, 10, 33, 4, 103]
print(sorted(a_list))
>> [1, 4, 8, 10, 33, 103]
If you call 
sorted
on a list of strings, Python will return a new list sorted alphabetically by each 
string’s first letter:
a_list = ["Guido van Rossum", "James Gosling", "Brendan Eich", "Yukihiro Matsumoto"]
print(sorted(a_list))
>> ['Brendan Eich', 'Guido van Rossum', 'James Gosling', 'Yukihiro Matsumoto']
Python’s 
sorted
function has an optional parameter called 
reverse
, so if you want to sort your 
iterable in descending order, you can pass in 
reverse=True
:
a_list = [1, 8, 10, 33, 4, 103]
print(sorted(a_list, reverse=True))
>> [103, 33, 10, 8, 4, 1]
Sorted
also has a parameter called 
key
that lets you pass in a function. Python then calls that 
function on each item in your iterable and uses the result to sort it. For example, you can pass in the 
len
function, which will sort a list of strings by length:
a_list = ["onehundred", "five", "seventy", "two"]
print(sorted(a_list, key=len))
>> ['two', 'five', 'seventy', 'onehundred']

---