Skip to content
Tutorials Center
My learning

Topics

Lesson 77 of 225 ยท Sorting

Sorting Basics

Understand sorting before you learn the algorithms: stability, in-place sorting, the n log n lower bound, and how to use sorted, sort, key and cmp_to_key in Python.

Sorting means putting items in order: numbers from small to large, names alphabetically, orders by date. It looks like a small chore, yet it is one of the most useful ideas in computing. Once data is sorted, you can binary search it in O(log n), spot duplicates by looking at neighbours, merge two lists in a single pass, and group equal things together.

This lesson is the foundation of the whole chapter. Before you meet bubble sort, merge sort or quick sort, you need the vocabulary that separates them (stable, in-place, comparison-based), you need to know why no comparison sort can beat O(n log n), and you need to know how to use Python's own sorting tools, which are what you will actually reach for in real code.

Why sort?

  • Faster search. A sorted list can be searched in O(log n) instead of O(n).
  • Easy duplicates and groups. Equal items end up next to each other.
  • Ranking and top-k. The largest items are at one end. See priority queues for when you only need a few of them.
  • Merging and sweeping. Many algorithms (merging intervals, two pointers, sweep lines) need sorted input first. See two pointers.
  • Readable output. People like ordered lists.

A common interview trick is "sort first, then the problem becomes easy". The price is O(n log n), which is often cheap compared with an O(nยฒ) brute force.

The vocabulary

TEXT
              input                         output
      [ 4, 1, 3, 1, 2 ]   --- sort --->   [ 1, 1, 2, 3, 4 ]

Comparison-based. The algorithm only learns about the data by asking "is a less than b?". Bubble, selection, insertion, merge, quick and heap sort all work this way. Counting and radix sort do not (see counting, radix and bucket sort).

In-place. The sort rearranges items inside the original array and uses only O(1) (or sometimes O(log n)) extra memory. Insertion sort is in-place; the classic merge sort is not, because it needs a helper array of size n.

Stable. A sort is stable if items that compare equal keep their original relative order. This matters as soon as items have more than one field. Suppose you sort people by age, and two people are both 30. A stable sort keeps them in the order they were in before.

TEXT
before:  (Mia, 30) (Zoe, 25) (Ali, 30) (Ben, 25)
stable by age:     (Zoe, 25) (Ben, 25) (Mia, 30) (Ali, 30)   <- Zoe before Ben, Mia before Ali
unstable (maybe):  (Ben, 25) (Zoe, 25) (Mia, 30) (Ali, 30)   <- Zoe and Ben swapped

Adaptive. An adaptive sort runs faster when the input is already nearly sorted. Insertion sort is adaptive: O(n) on sorted input. Selection sort is not.

Internal vs external. Internal sorts fit in memory. External sorts handle data bigger than memory by sorting chunks and merging them (see parallel and external algorithms).

Algorithm Best Average Worst Extra space Stable In-place
Bubble O(n) O(nยฒ) O(nยฒ) O(1) yes yes
Selection O(nยฒ) O(nยฒ) O(nยฒ) O(1) no yes
Insertion O(n) O(nยฒ) O(nยฒ) O(1) yes yes
Merge O(n log n) O(n log n) O(n log n) O(n) yes no
Quick O(n log n) O(n log n) O(nยฒ) O(log n) no yes
Heap O(n log n) O(n log n) O(n log n) O(1) no yes
Timsort (Python) O(n) O(n log n) O(n log n) O(n) yes no

Python's built-in sorting

In real programs, you almost never write your own sort. Python gives you two tools, both using Timsort, a stable, adaptive hybrid of merge sort and insertion sort (see Shell sort, Timsort and hybrid sorts):

  • sorted(iterable) returns a new list and works on any iterable (lists, tuples, strings, dict keys, generators).
  • list.sort() sorts a list in place and returns None.

Both accept key= (a function that computes the value to compare) and reverse=True.

Python sorted, sort, key and reverse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A very common beginner bug is numbers = numbers.sort(). Because list.sort() returns None, you end up with None and lose your list. Use numbers.sort() alone, or numbers = sorted(numbers).

Note how sorted(words, key=len) puts Apple before apple and keeps banana, cherry and Banana in their original relative order, because their lengths tie. That is stability at work. Also note that reverse=True preserves stability too: items that tie still keep their original order, so it is not the same as reversing the sorted result.

Sorting by several keys

Real data has several fields. There are two clean ways to sort by "department, then salary descending".

Way 1: a tuple key. Python compares tuples element by element. For numbers, negate a value to flip its direction.

Way 2: several stable passes. Because the sort is stable, you can sort by the least important key first, then by the most important one. Each pass keeps the order established by the previous one. This is the only option when a field cannot be negated (like a string you want descending).

Python Multi-key sorting two ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A custom comparison with cmp_to_key

Sometimes order is defined by a rule between two items, not by a single value you can compute for each one. Python 3 dropped the old cmp= argument, but functools.cmp_to_key converts a comparison function into a key.

A comparison function takes a and b and returns a negative number if a should come first, a positive number if b should come first, and zero if they are equal.

A classic example: given non-negative integers, arrange them so that joining them gives the largest possible number. Sorting by size does not work (30 is bigger than 3, yet "3" + "30" beats "30" + "3"). The rule is: a goes before b when a + b (as text) is bigger than b + a.

Python Largest joined number with cmp_to_key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Prefer key= whenever you can: it computes the key once per item, while a comparison function is called for every comparison. Use cmp_to_key only when the rule truly involves both items together.

Why no comparison sort beats O(n log n)

Here is a neat argument that explains why the good algorithms in this chapter all cluster around O(n log n).

Imagine a sort that only learns about the data by comparing two items at a time. With n distinct items there are n! possible input orders (n factorial: n x (n-1) x ... x 1). The algorithm must produce a different rearrangement for each one, so it has to be able to tell all n! orders apart.

Every comparison has two outcomes (yes/no), so it can at best split the remaining possibilities in half. Draw all the algorithm's possible questions as a decision tree: each internal node is a comparison, each leaf is a final ordering.

TEXT
                a < b ?
               /       \
         b < c ?        a < c ?
         /    \          /    \
     a b c   a < c?   b a c   b < c?
             /   \            /   \
         a c b   c a b     b c a   c b a      <- 3! = 6 leaves

A binary tree with L leaves has height at least log2(L). The tree needs at least n! leaves, so the number of comparisons in the worst case is at least log2(n!). And log2(n!) grows like n log2(n) (the product n! is at least (n/2) multiplied by itself n/2 times). Therefore every comparison-based sort needs ฮฉ(n log n) comparisons in the worst case.

This is a statement about comparison sorts only. Algorithms that look at the actual values, such as counting sort, can beat it for special data. We will see them in counting, radix and bucket sort.

Let us watch the bound in action by counting the comparisons Python's own sort makes.

Python Counting comparisons against log2(n!)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The "comparisons" column can never drop below the "ceil(log2(n!))" column, and it stays close to it: for 1024 items the theoretical minimum is 8,770 and Timsort used 8,952. Both are below the rough figure n x log2(n), which overestimates because n! is smaller than n to the power n. The last line shows Timsort's adaptivity: on input that is already in order, it needs a single pass of n - 1 = 1,023 comparisons, which is why its best case is O(n).

Choosing a sort

  • Just need sorted data in Python? Use sorted() or .sort(). They are fast, stable and well tested.
  • Small or nearly sorted data, simple code? Insertion sort.
  • Need guaranteed O(n log n) and stability? Merge sort.
  • Need in-place and fast on average? Quick sort, usually with a random pivot.
  • Need guaranteed O(n log n) with O(1) extra space? Heap sort.
  • Integers in a small range? Counting or radix sort.
  • Learning? Bubble and selection sort are slow but excellent for understanding. Nobody should use them in production code.

Common mistakes

  • Using list.sort() and expecting a return value.
  • Comparing mixed types, such as [3, "a"], which raises TypeError in Python 3.
  • Expecting sorted strings to be case-insensitive or number-aware: sorted(["10", "9"]) gives ["10", "9"], because text is compared character by character.
  • Implementing your own sort when sorted would do.
  • Forgetting that an unstable algorithm can scramble equal items, which breaks multi-pass sorting.
  • Writing a key function that returns different types for different items (for example a number for some and None for others), which raises TypeError.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does it mean for a sorting algorithm to be stable?

    Stability is about equal items. If two records have the same key, a stable sort leaves the one that came first in front. That is what makes multi-pass sorting by several keys work.
  2. 2. What does result = [3, 1, 2].sort() store in result?

    list.sort() sorts in place and returns None. Use sorted() when you want a new sorted list as the return value.
  3. 3. Why does every comparison-based sort need ฮฉ(n log n) comparisons in the worst case?

    Each comparison has two outcomes, so a tree of height h has at most 2^h leaves. To tell all n! input orders apart you need 2^h >= n!, hence h >= log2(n!), which is about n log n.
  4. 4. How do you sort employees by department ascending and salary descending with one sorted() call?

    A tuple key compares field by field. Negating the salary flips its direction while the department stays ascending.
  5. 5. When should you use functools.cmp_to_key?

    key= computes one value per item and is usually faster. cmp_to_key wraps a two-argument comparison function, which is handy for rules like 'a before b when a+b is bigger than b+a'.

Summary

  • Sorting speeds up searching, grouping, merging and ranking.
  • Stable keeps equal items in order; in-place uses O(1) extra memory; adaptive is faster on nearly sorted input.
  • Any comparison-based sort needs ฮฉ(n log n) comparisons in the worst case, because n! orders must be distinguished.
  • In Python, use sorted() (new list) or list.sort() (in place, returns None), with key= and reverse=.
  • Sort by several keys with a tuple key or by stable passes from the least to the most important key.
  • Use functools.cmp_to_key only for rules that compare two items together.
  • Next you will learn the algorithms behind sorting, starting with the simplest ones.

Next: Bubble Sort