In the previous lesson we discovered that binary search resolves in twenty comparisons what costs a linear search a million, but it demands a requirement EasyTask does not yet meet: that the data be sorted. We also said that sorting costs. It is time to find out how much and how, by opening the course's second black box: what sorted does inside.

Sorting is, probably, the most profitable operation you will learn. Not just because a sorted listing reads better: a sorted collection enables binary search, lets you spot duplicates at a glance, makes range reports trivial and turns "the five most urgent jobs" into a slice. In this lesson you will implement three classic algorithms with their step-by-step traces, understand what it means for a sort to be stable, and finish by using the real tool —sorted and .sort()— finally knowing what happens inside.

1. What sorting means and why it pays off
2. The sort criterion
3. Stability: why it matters at Alba Studio
4. Selection sort
5. Insertion sort
6. Bubble sort and the sentinel
7. The three algorithms, compared
8. Divide-and-conquer algorithms: mergesort and quicksort
9. Sorting in real Python
10. Measuring the difference with time.perf_counter()
11. EasyTask v0.13: priority, days and tomorrow's plan
12. Common mistakes and tips
13. Exercises
14. Conclusion

Sorting means rearranging the elements of a collection so that each one is "less than or equal to" the next according to some criterion. The definition hides two decisions you have to take before writing a single line: what gets compared and what happens with ties. The first is the sort criterion, the second is stability, and the next two sections deal with them.

What makes sorting an investment rather than an expense is everything it enables afterwards:

That is why sorting once and querying many times almost always beats querying without sorting. It is the same reasoning as the inverted index from 06-01: pay an up-front cost so everything that comes afterwards is cheap.

Numbers and text have a natural order (3 < 7, "Luis" < "Marta" by the character order you saw in 05-02), but a dictionary does not: nobody knows whether "the poster task" is greater or smaller than "the menu one". The sort criterion is the rule that turns each element into something comparable.

That key is the callback from 04-05: a function that takes an element and returns the value it is compared by. Every algorithm in this lesson is written first comparing numbers, because that is where the mechanism shows, and generalised afterwards with key. The key idea is that the sorting algorithm and the criterion are separate things: the same algorithm sorts by days, by title or by priority just by changing the comparison function.

A sort is stable when elements that tie keep the order they already had. It sounds like an academic subtlety until you see a real case.

Marta sorts the agenda by estimated days, fewest first, so she sees what can be cleared quickly:

Then she re-sorts it by priority. With a stable sort, inside "high" the previous order is preserved: first Vidal logo (2 days) and then Book fair poster (3). The result is what Marta wanted: sorted by priority and, within equal priority, by days. With an unstable sort, those two tasks could come out in any order and the work of the first sort would be lost.

Hence the classic technique: to sort by several criteria, sort by the least important first and by the most important last, and stability preserves the earlier work. In section 9 you will see the modern alternative, which is clearer still. And hold on to this fact: Python's sorted() and .sort() are stable, always, and that is guaranteed by the language.

The idea is the one you would use with a hand of cards: find the smallest of all, put it first; find the smallest of the rest, put it second, and so on.

Three things to understand here. The outer loop walks the positions that get fixed one by one; it goes up to n - 1 because when a single element is left it is necessarily already in place. The inner loop is the minimum-finding pattern from 03-02, but storing the position and not the value, because we have to swap. And the swap a, b = b, a is the tuple unpacking from 05-04 doing its job with no auxiliary variable.

Trace over the estimated days [3, 5, 2, 4, 1]:

Look at pass 4: the list was already sorted and the algorithm still did the full pass. Selection sort never realises it has finished: it always does exactly the same number of comparisons, whether the list arrives sorted or backwards. In exchange, it makes very few swaps: one per pass at most, which makes it interesting when moving an element is expensive.

And an important warning for section 7: classic selection sort is not stable, precisely because of that long-distance swap, which can jump an equal element over another.

This is the one everybody uses when sorting cards in their hand: you pick up the next one and place it where it belongs among the already sorted ones, shifting the bigger ones to the right.

The delicate part is the while, and it is worth reading slowly. It steps back from the previous position as long as two conditions hold: that we have not fallen off the left edge (j >= 0) and that the element examined is greater than the one we are holding. The order of those two conditions is not accidental: thanks to the lazy evaluation of and you saw in 02-02, if j reaches -1 the second comparison is never evaluated, so values[-1] is never accessed, which in Python would be the last element and would produce a silent bug.

Trace over [3, 5, 2, 4, 1]; the already sorted part is in bold:

Here is insertion sort's great virtue, and the reason it is still alive in professional software: with almost-sorted data it is blisteringly fast. If every element is already near its place, the while runs once or not at all and the whole sort costs barely more than one sweep. Over an already sorted list, insertion sort makes a single comparison per element and no shifts: it is the best possible case. And it is stable, because the while stops the moment it finds an equal element and never jumps over it.

Bubble sort compares neighbours and swaps the ones that are the wrong way round, pass after pass, until none is out of order. On every pass the largest of the remaining ones "floats" up to the end, hence the name.

Two improvements live together in this code. The range(n - 1 - pass_number) shortens each pass, because after the first one the last element is already the largest and does not need looking at again. And swapped is the sentinel: the flag pattern from 03-02 applied here. If a whole pass swaps nothing, the list is sorted and the break leaves the loop. Without the sentinel, bubble sort would always do every pass even if the list arrived already sorted.

Trace over [3, 5, 2, 4, 1], showing the state at the end of each pass:

With five elements, range(n - 1) gives four passes and here every one of them is used. But if the input list were [1, 2, 3, 4, 5], the first pass would swap nothing, swapped would stay False and the break would finish the job with four comparisons in total. That is the whole value of the sentinel.

Bubble sort is stable —it only swaps strictly out-of-order neighbours, never equal ones— and it is, in practice, the slowest of the three, because it makes an enormous number of swaps. It is taught because its mechanism is visible at a glance, not because it gets used.

The three share one thing you can see in the code: two nested loops. Remember what was said in 03-03: with two nested loops, doubling the data quadruples the work. Ten elements are about a hundred operations; a thousand elements, a million. That is their ceiling, and in Efficiency and Big-O Notation we will give it a formal name.

If you had to keep just one to implement by hand, it is insertion sort: it is stable, it is simple and it is the best with almost-sorted data, which is the most common situation in real life (an agenda that gets a task appended at the end is already almost sorted).

The three algorithms above share a ceiling they cannot get below with their strategy. To beat it you have to change the idea: instead of sweeping the list over and over, split it into chunks, sort each chunk and combine the results. That strategy is called divide and conquer, and out of it come the two algorithms that actually get used. Merge sort (mergesort) splits the list down the middle, sorts each half and merges the two sorted halves in a single pass; it is stable and its performance does not depend on the input data. Quicksort picks an element as the pivot, puts the smaller ones on the left and the larger ones on the right, and repeats on each side; it is faster in practice, but it is not stable and it has a bad case.

The difference in scale is brutal: where bubble sort needs a million operations for a thousand elements, these need about ten thousand. Both rely on an algorithm calling itself on the smaller chunks, so they need a tool you do not have yet. You will meet it in the next lesson, and there we will implement the full mergesort with its trace: the idea of splitting is picked up again in Recursion.

Everything above exists so you understand the mechanism. In a real program you use what the language provides, and Python provides two ways of sorting that are worth not confusing:

operator.itemgetter("days") builds a function that does exactly the same as lambda t: t["days"], but it is written in C and reads better when there are several fields. And that last line is the modern technique for sorting by several criteria: the key returns a tuple, and Python compares tuples element by element —the first one first, and only if they tie does it look at the second—, which is exactly what "by priority and, within the same one, by days" means.

That PRIORITY_ORDER dictionary, which EasyTask has had since v0.10, solves a real problem: alphabetically "high" comes before "low" and "medium", which is pure coincidence and not the order we want. Translating each priority into a number imposes the logical order instead of the alphabetical one. And if you wanted to reverse only one of the two criteria and not the other, the usual trick with numbers is to negate them: (-t["days"], t["title"]) sorts by days from most to fewest and, on ties, by title from A to Z.

And what is inside sorted? An algorithm called Timsort, written by Tim Peters for Python in 2002 and adopted afterwards by Java and Android. It is a hybrid: it detects the stretches that are already sorted in real data —and there almost always are some—, sorts the short stretches with insertion sort, the very one from section 5, and merges them with the mergesort technique. It is stable and it exploits pre-existing order, so over an almost-sorted list it comes close to a single pass.

Arguing without measuring is just having an opinion. time.perf_counter() returns a high-precision number of seconds; the difference between two readings is the elapsed time.

The copy with list(data) is essential: since these algorithms sort in place, without it the second measurement would receive an already sorted list and the result would be a lie. Approximate results on an ordinary laptop —yours will vary, but the proportions will hold:

Read the table vertically, which is where the lesson lives. Multiplying the data by ten takes sorted from 0.0002 to 0.003 seconds —about fifteen times more—, while bubble sort goes from 0.09 to 11 seconds, more than a hundred times more. That is the difference between an algorithm with two nested loops and one that divides, and that is why no amount of programming tricks will save a badly chosen algorithm.

The usual moral, this time backed by numbers: in production you use sorted() or .sort(). They are written in C, they are stable, they exploit pre-existing order and no implementation of yours will get near them. The above is implemented so you understand what they do inside and know how to choose.

We apply what we have learned in two places. The listing now sorts by two criteria with a tuple key, and we add the report Marta asks for every afternoon: what each team member is doing tomorrow. The menu grows to nine options.

Design decisions worth pointing out:

• sort_key is a named function, not a lambda. It is used in two different places and deserves a docstring explaining the criterion; it is exactly the threshold we set in 04-05 for promoting a lambda to a def.
• The key returns a three-element tuple, with the title as the third tie-breaker. That way the listing comes out always identical for the same data, without depending on the order things were registered in. A listing that changes order for no reason baffles the user.
• tomorrow_plan combines the module's two lessons: the inverted index from 06-01 to group by person and the two-criteria sort to pick each person's most urgent task. pending[0] is the answer to "where do I start tomorrow?" precisely because the list is sorted.
• Sorting happens on display, not on saving. The agenda lives in the order it was registered in; the order is a presentation decision. Sorting the real list would force a re-sort after every change and would lose the registration order, which is a piece of data in itself.

Expecting .sort() to return the sorted list. sorted_list = agenda.sort() leaves sorted_list holding None, and the error shows up later and far away, when something tries to sweep that None. The rule: .sort() modifies, sorted() returns.

Sorting alphabetically something that has its own order. sorted(agenda, key=lambda t: t["priority"]) puts "high", "low" and "medium" in that order, which is not the one you want. Translate to numbers with a dictionary like PRIORITY_ORDER.

Modifying the list while sorting or sweeping it. Adding or deleting elements inside the loop that sweeps it produces unpredictable results and skipped elements. Build a new list and substitute it at the end.

Confusing the element with its position in selection sort. If you store min_pos = values[j] instead of min_pos = j, afterwards you will not know where it was and the swap becomes impossible.

Forgetting the copy when timing. If you measure two algorithms over the same list, the second one gets already sorted data and looks miraculously fast. list(data) before every measurement.

Tip: sort once, not on every query. If the listing is asked for ten times without the agenda changing, sort once and store the result. And if you need to keep a collection permanently sorted while inserting, bisect.insort from 06-01 places each element where it belongs without re-sorting anything.

Tip: if you only need the best ones, do not sort. For "the three most urgent tasks" of a huge list, heapq.nsmallest(3, agenda, key=sort_key) is cheaper than sorting everything and keeping [:3].

Trace in two tables the sorting of the list [4, 1, 5, 2] with insertion sort (one row per pass, giving the element held in hand and the resulting list) and with bubble sort with a sentinel (one row per pass, giving the swaps and the value of the sentinel). State how many comparisons each one makes and how many bubble sort would make if the list arrived already sorted.

Adapt selection_sort so it accepts a key parameter —a function, like sorted's key— with a default value that leaves the element as it is, and sorts by comparing key(element). Then use it to sort the agenda by days and by title, and check with sorted that the result matches.

Write is_sorted(values, key=None) returning True if the list is already sorted from smallest to largest by that criterion, sweeping it just once and leaving the moment it finds an out-of-order pair. Then write sort_if_needed(agenda), which uses the previous one so as not to sort in vain, and reports on screen what it has done.

Solution 1. Insertion sort over [4, 1, 5, 2]:

Five comparisons in total. Bubble sort with a sentinel over the same list:

Three plus two plus one: six comparisons. If the list arrived already sorted, the first pass would make three comparisons and no swaps, and the sentinel would cut it off there: three comparisons in total.

Solution 2.

The change is minimal —three appearances of key(...) in the comparison— and it turns an algorithm that only sorted numbers into one that sorts anything: it is the callback pattern from 04-05 all over again. Watch that last line: the comparison with sorted gives True if there are no ties in the days; if there are it may give False, and not because the result is wrong, but because our selection sort is not stable and sorted is. It is the best way to see stability with your own eyes.

Solution 3.

is_sorted is a linear search from 06-01 in disguise: it looks for the first out-of-order pair and leaves the moment it finds one. Checking costs a single sweep, vastly less than sorting, so the preliminary check pays off whenever there is a reasonable chance that it is already sorted. And notice that sort_if_needed returns the agenda on both paths, sorted or not: a function that sometimes returns something and sometimes does not is an inexhaustible source of bugs, as was said in 04-02.

Sorting means rearranging by a sort criterion, that key function which says what gets compared in each element, and with a property that decides what happens to ties: stability, which preserves the previous order of equal items and lets you sort by several criteria by chaining sorts. You have implemented and traced the three classic algorithms: selection sort, which finds the smallest and places it, makes few swaps but always the same amount of work and is not stable; insertion sort, which places each element where it belongs inside the already sorted part, is stable and excellent with almost-sorted data; and bubble sort, which swaps neighbours and, with the sentinel, knows to stop when there is nothing left to do, but is still the slowest. All three share two nested loops and, with them, a ceiling: a thousand elements are a million operations.

That ceiling only breaks by changing strategy, splitting the list into chunks as mergesort and quicksort do. In the meantime, in production you use sorted() —which returns a new list— or .sort() —which modifies in place and returns None—, with reverse, with key (a lambda or an operator.itemgetter) and, for several criteria at once, with a tuple as the key. Inside they carry Timsort, a stable hybrid of insertion and merging that exploits already-sorted stretches; and the measurements with time.perf_counter() have put numbers on the difference: 3,600 times faster than our bubble sort with 10,000 elements. EasyTask reaches v0.13 with the listing sorted by priority and days and with the tomorrow's plan Marta hands out every afternoon.

One piece is still pending, and it shows up in both places where we had to stop. The binary search from 06-01 had a more elegant version we could not write, and this lesson's mergesort needs to sort two halves which are, in turn, lists waiting to be sorted. Both ask for the same thing: a function that calls itself. In Recursion you will see how a function can solve a problem by solving smaller versions of itself, which two pieces can never be missing, and why recursion, badly used, repeats work until it becomes useless.