Sorting

Understanding how sorting works is essential even if you always use the built-in methods in practice.

Python’s Built-in Sort

list.sort() sorts in place (modifies the list, returns None). sorted(iterable) returns a new sorted list without modifying the original. Try it live and watch sort modify the list in place:

Try it live ▶

>>> nums = [3, 1, 4, 1, 5, 9, 2]
>>> nums.sort()
>>> print(nums)
[1, 1, 2, 3, 4, 5, 9]

Go BackOpen In Tab

The key and reverse arguments control how sorted() orders items. Try it live: sort by len, in reverse, or with your own key:

Try it live ▶

>>> words = ["banana", "apple", "cherry", "fig"]
>>> print(sorted(words))               # alphabetical
['apple', 'banana', 'cherry', 'fig']
>>> print(sorted(words, key=len))      # by length
['fig', 'apple', 'banana', 'cherry']
>>> print(sorted(words, reverse=True)) # reverse alphabetical
['fig', 'cherry', 'banana', 'apple']

Go BackOpen In Tab

Functions as Values

Look again at sorted(words, key=len). You did not call len — you handed the function itself to sorted and let it do the calling. In Python a function is a value like any other: you can store it in a variable, pass it to another function, or return it. A function that takes another function as an argument (the way sorted takes key) is called a higher-order function.

When the function you want to pass is small, naming it with def is more trouble than it is worth. A lambda is a short, unnamed function written inline. You write the keyword lambda, then its parameters, a colon, and a single expression. So lambda w: w[-1] reads as “given w, give back w[-1], its last letter” — the same as a one-line def that returns w[-1], but with no name and no return keyword. A lambda is a single expression, and its value is whatever that expression produces. Lambdas earn their place when there is no built-in that does what you need:

Try it live ▶

>>> words = ["banana", "apple", "cherry", "fig"]
>>> print(sorted(words, key=lambda w: w[-1]))        # by last letter
['banana', 'apple', 'fig', 'cherry']
>>> print(sorted(words, key=lambda w: (len(w), w)))  # length, then alphabetical
['fig', 'apple', 'banana', 'cherry']

Go BackOpen In Tab

The second key, lambda w: (len(w), w), returns a tuple, so the words sort by length first and then alphabetically among ties.

Passing small functions around like this is your first taste of functional thinking, and it pairs with a second idea you have already met. sorted returns a new list; list.sort changes the list in place. sorted is a pure function: it computes a result from its arguments and does nothing else, so the same input always gives the same output. list.sort has a side effect: it modifies something and returns None.

Try it live ▶

>>> nums = [3, 1, 2]
>>> result = sorted(nums)    # pure: builds a new list
>>> print(result, nums)      # original untouched
[1, 2, 3] [3, 1, 2]
>>> nums.sort()              # side effect: changes nums
>>> print(nums)
[1, 2, 3]

Go BackOpen In Tab

Neither style is wrong. Pure functions are easier to test and reason about, because you only have to think about what goes in and what comes out. Side effects are how a program changes the world — printing, writing files, updating a list in place. The skill is knowing which one you are using. We come back to functional thinking — map, filter, and writing your own higher-order functions — in the Functional Programming chapter.

Selection Sort

Selection sort finds the minimum of the unsorted portion and swaps it into place. It always makes exactly N-1 swaps, but O(N²) comparisons:

def selection_sort(data: list) -> None:
    """Sort data in place using selection sort — O(N²)."""
    n = len(data)
    for i in range(n):
        min_pos = i
        for j in range(i + 1, n):
            if data[j] < data[min_pos]:
                min_pos = j
        data[i], data[min_pos] = data[min_pos], data[i]

nums = [12, 8, -5, 22, 9, 2]
selection_sort(nums)
print(nums)

Output:

[-5, 2, 8, 9, 12, 22]

Python’s tuple-assignment swap a, b = b, a eliminates the need for a temporary variable.

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order. After each pass the largest unsorted element “bubbles” to its correct position. Both swaps and comparisons are O(N²):

def bubble_sort(data: list) -> None:
    """Sort data in place using bubble sort — O(N²)."""
    n = len(data)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]

nums = [12, 8, -5, 22, 9, 2]
bubble_sort(nums)
print(nums)

Output:

[-5, 2, 8, 9, 12, 22]

Insertion Sort

Insertion sort builds a sorted sublist from the left, inserting each new element into its correct position. It is efficient for nearly-sorted data:

def insertion_sort(data: list) -> None:
    """Sort data in place using insertion sort — O(N²), efficient for nearly-sorted data."""
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key

nums = [12, 8, -5, 22, 9, 2]
insertion_sort(nums)
print(nums)

Output:

[-5, 2, 8, 9, 12, 22]

Algorithm Comparison

Algorithm	Comparisons	Swaps
Bubble sort	O(N²)	O(N²)
Selection sort	O(N²)	O(N)
Insertion sort	O(N²) avg	O(N²) avg
Python sort()	O(N log N)	O(N log N)

For any real application use list.sort() or sorted(). Study the O(N²) algorithms to understand the problem; use the built-in to solve it.