Sorting Algorithms in Python: Bubble to Merge

Sorting means putting items in order, such as numbers from small to large or names from A to Z. It is one of the most studied problems in computer science, because so many other things get easier once the data is sorted: searching (see Binary Search in Python), finding duplicates, and merging lists.

In everyday Python you will just call sorted(). But interviews, and understanding how algorithms behave, call for knowing how sorting works inside. This guide covers the built-in tools first, then five classic algorithms: bubble, selection, insertion, merge and quick sort. We count comparisons instead of seconds, so the numbers are the same on every computer. All the output shown is real.

The built-in way: sorted() and sort()

sorted(x) returns a new sorted list and leaves the original alone. It accepts any iterable. list.sort() sorts the list in place and returns None. Both take reverse=True and a key function that says what to sort by:

nums = [5, 2, 9, 1, 5, 6]
print(sorted(nums))
print(sorted(nums, reverse=True))
print(nums)                        # sorted() does not change the original

nums.sort()                        # sort() changes the list itself
print(nums)

words = ["pear", "Fig", "apple", "kiwi"]
print(sorted(words))
print(sorted(words, key=str.lower))
print(sorted(words, key=len))

Output

[1, 2, 5, 5, 6, 9]
[9, 6, 5, 5, 2, 1]
[5, 2, 9, 1, 5, 6]
[1, 2, 5, 5, 6, 9]
['Fig', 'apple', 'kiwi', 'pear']
['apple', 'Fig', 'kiwi', 'pear']
['Fig', 'pear', 'kiwi', 'apple']

Plain sorted(words) puts 'Fig' first because uppercase letters sort before lowercase ones. Using key=str.lower fixes that. The key function is called once per item, and the items are compared by the keys it returns. Python uses Timsort, a hybrid of merge sort and insertion sort that is O(n log n) in the worst case and close to O(n) on data that is already mostly in order.

Stability and multiple keys

A sort is stable if items that compare equal stay in their original order. Python’s sort is stable, so in the first result below Ben stays ahead of Dev, and Asha ahead of Chen, as they were in the input. To sort by several fields, return a tuple from key. A minus sign flips a number, which gives “age descending, then name A to Z”:

people = [("Asha", 30), ("Ben", 25), ("Chen", 30), ("Dev", 25)]
print(sorted(people, key=lambda p: p[1]))
print(sorted(people, key=lambda p: (-p[1], p[0])))

scores = {"a": 3, "b": 1, "c": 2}
print(sorted(scores.items(), key=lambda kv: kv[1], reverse=True))

Output

[('Ben', 25), ('Dev', 25), ('Asha', 30), ('Chen', 30)]
[('Asha', 30), ('Chen', 30), ('Ben', 25), ('Dev', 25)]
[('a', 3), ('c', 2), ('b', 1)]

The last line shows the usual way to sort a dictionary by its values. (Dictionaries are covered in Python Dictionaries Explained, and lambdas in Lambda, map, filter and reduce.)

Bubble sort

Compare neighbours and swap them if they are in the wrong order. After one pass over the list, the largest item has “bubbled” to the end. Repeat for the shorter unsorted part. If a whole pass makes no swaps, the list is sorted and we stop early:

def bubble_sort(items):
    items = items[:]                  # work on a copy
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:               # a pass with no swaps: already sorted
            break
    return items

print(bubble_sort([5, 2, 9, 1, 5, 6]))

Output

[1, 2, 5, 5, 6, 9]

The passes on [5, 2, 4, 1]:

items = [5, 2, 4, 1]
print("start :", items)
for end in range(len(items) - 1, 0, -1):
    for i in range(end):
        if items[i] > items[i + 1]:
            items[i], items[i + 1] = items[i + 1], items[i]
    print("pass  :", items, "<- the largest is now at the end")

Output

start : [5, 2, 4, 1]
pass  : [2, 4, 1, 5] <- the largest is now at the end
pass  : [2, 1, 4, 5] <- the largest is now at the end
pass  : [1, 2, 4, 5] <- the largest is now at the end

It is easy to understand but slow: about n²/2 comparisons. It is mainly used for teaching.

Selection sort

Find the smallest item in the unsorted part and swap it to the front. Then find the next smallest, and so on. It does at most n - 1 swaps, which is handy when writing is expensive, but it always makes the same number of comparisons, even on sorted data:

def selection_sort(items):
    items = items[:]
    for i in range(len(items)):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
    return items

print(selection_sort([5, 2, 9, 1, 5, 6]))

Output

[1, 2, 5, 5, 6, 9]

Insertion sort

This is how many people sort playing cards. Take the next item and slide it left past every bigger item, into its correct spot among the ones already sorted. On data that is already almost sorted, each item barely moves, so it runs close to O(n). That is why insertion sort is used for small or nearly sorted lists, and inside Timsort:

def insertion_sort(items):
    items = items[:]
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]   # shift bigger items to the right
            j -= 1
        items[j + 1] = current
    return items

print(insertion_sort([5, 2, 9, 1, 5, 6]))

Output

[1, 2, 5, 5, 6, 9]

Merge sort

Merge sort uses divide and conquer (a recursive idea, see Recursion in Python Explained Simply). Split the list in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. The same merge step is used for linked lists in Linked List in Python:

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])

    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # <= keeps equal items in their original order
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([5, 2, 9, 1, 5, 6]))

Output

[1, 2, 5, 5, 6, 9]

Here are the merges on four items. First the halves of size one are merged, then the halves of size two:

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:] + right[j:]
    print("merge", left, "and", right, "->", merged)
    return merged

merge_sort([5, 2, 4, 1])

Output

merge [5] and [2] -> [2, 5]
merge [4] and [1] -> [1, 4]
merge [2, 5] and [1, 4] -> [1, 2, 4, 5]

The list is halved about log n times, and every level of merging touches all n items, hence O(n log n) in every case. The price is O(n) extra memory for the merged lists. It is also stable, thanks to <= in the comparison.

Quick sort

Pick a pivot. Put everything smaller on one side and everything larger on the other, then sort each side the same way. The pivot’s final position is already fixed. This version is written for readability, with list comprehensions. The real in-place version does the same job with swaps and no extra lists:

def quick_sort(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    return quick_sort(smaller) + equal + quick_sort(larger)

print(quick_sort([5, 2, 9, 1, 5, 6]))

Output

[1, 2, 5, 5, 6, 9]

On average the two sides are roughly equal, so it is O(n log n) and very fast in practice. If the pivot is always the smallest or largest item, one side is empty every time, and the cost becomes O(n²). Always picking the first item as the pivot is the classic mistake, because sorted input then triggers that worst case. Picking the middle item (as here) or a random one makes it unlikely.

Comparing them by counting

How do you compare algorithms without a stopwatch? Count how many comparisons each one makes. The Counted class below wraps a number and adds one to a counter every time it is compared, so we can run the same functions unchanged. The same 1000 numbers are sorted in a scrambled order, and again already in order:

class Counted:
    """A number that counts every comparison made on it."""
    comparisons = 0

    def __init__(self, v):
        self.v = v

    def __lt__(self, other):
        Counted.comparisons += 1
        return self.v < other.v

    def __le__(self, other):
        Counted.comparisons += 1
        return self.v <= other.v

    def __gt__(self, other):
        Counted.comparisons += 1
        return self.v > other.v

    def __eq__(self, other):
        Counted.comparisons += 1
        return self.v == other.v

scrambled = [(i * 7919) % 1000 for i in range(1000)]    # 0..999 in a mixed-up order
in_order = list(range(1000))

print("comparisons for 1000 items".ljust(28), "scrambled", "already sorted")
for name, fn in [("bubble", bubble_sort), ("selection", selection_sort), ("insertion", insertion_sort),
                 ("merge", merge_sort), ("quick", quick_sort)]:
    row = []
    for data in (scrambled, in_order):
        Counted.comparisons = 0
        result = fn([Counted(x) for x in data])
        assert [c.v for c in result] == sorted(data)
        row.append(Counted.comparisons)
    print(name.ljust(28), str(row[0]).rjust(9), str(row[1]).rjust(14))

Counted.comparisons = 0
sorted([Counted(x) for x in scrambled])
under = Counted.comparisons < 10_000
Counted.comparisons = 0
sorted([Counted(x) for x in in_order])
print("built-in sorted(): under 10,000 comparisons when scrambled:", under, "| when already sorted:", Counted.comparisons)

Output

comparisons for 1000 items   scrambled already sorted
bubble                          498324            999
selection                       499500         499500
insertion                       251100            999
merge                             8415           4932
quick                            33282          25494
built-in sorted(): under 10,000 comparisons when scrambled: True | when already sorted: 999

Look at the difference. On scrambled data, the three simple sorts need between 250,000 and 500,000 comparisons, while merge sort needs about 8,400. Quick sort needs about 33,000 here, because this readable version compares every item three times per level (smaller, equal, larger). The in-place version compares each item once per level and needs far fewer. On sorted data, bubble and insertion sort finish after 999 comparisons, since they notice that nothing is out of place, while selection sort still makes half a million. The built-in sorted() needs only 999 there too, and on scrambled data it stays under 10,000, which is about n log n for 1000 items. Its exact count on scrambled data varies a little between Python versions, so the output shows only what holds everywhere.

Summary table

No algorithm that works only by comparing items can beat O(n log n) in the worst case. (See Big O Notation in Python for the notation.) Every implementation above is checked against sorted(), including the empty list, one item, duplicates and reversed input, and each one leaves the original list unchanged:

cases = [[], [1], [2, 1], [1, 2, 3, 4], [4, 3, 2, 1], [3, 1, 3, 1, 3], [5, 2, 9, 1, 5, 6]]
for fn in [bubble_sort, selection_sort, insertion_sort, merge_sort, quick_sort]:
    ok = all(fn(c) == sorted(c) for c in cases)
    print(fn.__name__.ljust(15), ok)

original = [3, 1, 2]
bubble_sort(original)
print(original)

Output

bubble_sort     True
selection_sort  True
insertion_sort  True
merge_sort      True
quick_sort      True
[3, 1, 2]

Common mistakes

• Writing x = items.sort(). sort() returns None. Use sorted() if you want a new list.
• Mixing types. Sorting numbers and strings together raises TypeError.
• Sorting the original by accident. sort() changes the list in place. Use sorted() or copy first if you still need the original order.
• Using a comparison function. Python wants a key, not a two-argument comparison. If you have one, functools.cmp_to_key converts it.
• Forgetting stability. When sorting on several fields, sort by the least important first, or use a tuple key.
• Writing your own sort in real code. Use the built-in. Writing your own is for learning and interviews.

nums = [3, 1, 2]
result = nums.sort()
print(result)

try:
    sorted([3, "a", 1])
except TypeError as e:
    print(type(e).__name__)

Output

None
TypeError

Try it yourself

Work out each answer first, then open the solution.

1. Sort ["pear", "fig", "apple", "kiwi"] by length, and alphabetically when the lengths are equal.

words = ["pear", "fig", "apple", "kiwi"]
print(sorted(words, key=lambda w: (len(w), w)))

['fig', 'kiwi', 'pear', 'apple']

2. Write is_sorted(items) that checks whether a list is in ascending order.

def is_sorted(items):
    return all(a <= b for a, b in zip(items, items[1:]))

print(is_sorted([1, 2, 2, 5]), is_sorted([1, 3, 2]), is_sorted([]))

True False True

3. Sort students by score, highest first. Asha and Chen have the same score. Who comes first, and why?

grades = [("Asha", 82), ("Ben", 91), ("Chen", 82), ("Dev", 75)]
top = sorted(grades, key=lambda g: -g[1])
print(top)

[('Ben', 91), ('Asha', 82), ('Chen', 82), ('Dev', 75)]

4. Which algorithm would you choose for a list that is nearly sorted, and why?

Run these in our free Python compiler.

Frequently asked questions

How do you sort a list in Python?

Use sorted(items) to get a new sorted list, or items.sort() to sort the list in place. Add reverse=True for descending order and key=... to choose what to sort by.

What sorting algorithm does Python use?

Timsort, a hybrid of merge sort and insertion sort. It is stable, takes O(n log n) in the worst case, and is close to O(n) on data that is already partly sorted.

What is the difference between sort() and sorted()?

sorted() works on any iterable and returns a new list. list.sort() works only on lists, changes them in place and returns None.

Which sorting algorithm is the fastest?

For general data, merge sort and quick sort are the fastest classic ones at O(n log n), and Python’s built-in Timsort is faster still in practice. Bubble, selection and insertion sort are O(n²).

What does a stable sort mean?

It means that items with equal keys keep their original relative order. This matters when sorting by several fields one after another. Python’s sorted() and sort() are stable.

When would I write my own sort in Python?

Almost never in real code. Implement the algorithms to learn how they work, to prepare for interviews, or for special cases such as sorting data that does not fit in memory.

Related reading

• Binary Search in Python: 3 Common Variations – what sorted data lets you do.
• Recursion in Python Explained Simply – the idea behind merge and quick sort.
• Big O Notation Explained With Python Examples – what O(n log n) and O(n²) mean.
• Python lambda, map, filter and reduce Explained – the key functions used above.