By WebNest Studio Engineering Team
Python Tutorial
Sorting Algorithms in Python
Sorting is everywhere — leaderboards, search results, reports — and sorting algorithms are the classic way to learn algorithmic thinking and complexity analysis. In real Python code you will almost always use the built-in sorted() and list.sort(), which use the highly optimised Timsort. Knowing how the classic algorithms work is still essential for interviews and for understanding performance.
This lesson implements bubble, selection, insertion, merge, quick and heap sort, explains Timsort, and compares their time complexity, stability and memory use.
Why it matters
In real code you call sorted(), which is fast and well tested. The classic sorting algorithms are studied because they are the clearest way to learn how to analyse the cost of code, and because interviewers use them to see how you reason about loops and comparisons. Knowing that Python's sort is stable also explains how sorting by several fields works.
Simple O(n²) Sorts
Bubble sort repeatedly swaps adjacent out-of-order items so the largest "bubbles" to the end; with an early-exit flag it is O(n) on already-sorted data. Selection sort repeatedly selects the smallest remaining item and puts it in place — always O(n²), but few swaps. Insertion sort builds a sorted prefix by inserting each new item into place — fast for small or nearly sorted lists, which is why Timsort uses it internally.
Efficient O(n log n) Sorts
Merge sort splits the list in half, sorts each half recursively and merges them — always O(n log n), stable, but needs O(n) extra memory. Quick sort partitions around a pivot and sorts each side — O(n log n) on average, O(n²) in the worst case (mitigated by random pivots). Heap sort builds a heap and extracts the minimum repeatedly — O(n log n) with O(1) extra memory, but not stable.
Timsort: Python's Built-in Sort
Timsort (created by Tim Peters for Python) finds already-ordered "runs" in the data, extends short runs with insertion sort, and merges runs efficiently. It is O(n log n) in the worst case, O(n) on sorted data, and stable — equal items keep their original order, which lets you sort by several keys in successive passes.
Comparison
Summary of the algorithms:
- Bubble — best O(n), average/worst O(n²), stable, in place.
- Selection — O(n²) always, not stable, in place.
- Insertion — best O(n), worst O(n²), stable, in place.
- Merge — O(n log n) always, stable, O(n) extra memory.
- Quick — average O(n log n), worst O(n²), not stable, in place.
- Heap — O(n log n), not stable, in place.
- Timsort — best O(n), worst O(n log n), stable (Python's sorted/sort).
Time complexity
| Operation | Average | Worst case |
|---|---|---|
| Bubble, selection and insertion sort | O(n²) | O(n²) |
| Merge sort and heap sort | O(n log n) | O(n log n) |
| Quick sort | O(n log n) | O(n²) |
Timsort (sorted, list.sort) | O(n log n) | O(n log n) |
Examples
Bubble, selection and insertion sort
def bubble_sort(items):
a = items[:]
for end in range(len(a) - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return a
def selection_sort(items):
a = items[:]
for i in range(len(a)):
smallest = min(range(i, len(a)), key=a.__getitem__)
a[i], a[smallest] = a[smallest], a[i]
return a
def insertion_sort(items):
a = items[:]
for i in range(1, len(a)):
current, j = a[i], i - 1
while j >= 0 and a[j] > current:
a[j + 1] = a[j]
j -= 1
a[j + 1] = current
return a
data = [64, 25, 12, 22, 11, 90, 5]
print(bubble_sort(data))
print(selection_sort(data))
print(insertion_sort(data))
[5, 11, 12, 22, 25, 64, 90]
[5, 11, 12, 22, 25, 64, 90]
[5, 11, 12, 22, 25, 64, 90]
Merge sort, quick sort and heap sort
import heapq
import random
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[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
return merged + left[i:] + right[j:]
def quick_sort(a):
if len(a) <= 1:
return a
pivot = random.choice(a)
return (quick_sort([x for x in a if x < pivot])
+ [x for x in a if x == pivot]
+ quick_sort([x for x in a if x > pivot]))
def heap_sort(a):
heap = a[:]
heapq.heapify(heap)
return [heapq.heappop(heap) for _ in range(len(heap))]
data = [38, 27, 43, 3, 9, 82, 10, 27]
print(merge_sort(data))
print(quick_sort(data))
print(heap_sort(data))
[3, 9, 10, 27, 27, 38, 43, 82]
[3, 9, 10, 27, 27, 38, 43, 82]
[3, 9, 10, 27, 27, 38, 43, 82]
Timsort in practice: stability and multi-key sorting
students = [("Asha", "B", 88), ("Ravi", "A", 72), ("Meera", "B", 95), ("Kiran", "A", 72)]
# Stable sorting: sort by the secondary key first, then by the primary key
by_name = sorted(students, key=lambda s: s[0])
by_section_then_name = sorted(by_name, key=lambda s: s[1])
print([s[0] for s in by_section_then_name])
# Or in one pass with a tuple key: highest marks first, then name
ranked = sorted(students, key=lambda s: (-s[2], s[0]))
print([(s[0], s[2]) for s in ranked])
['Kiran', 'Ravi', 'Asha', 'Meera']
[('Meera', 95), ('Asha', 88), ('Kiran', 72), ('Ravi', 72)]
Comparing speed on the same data
import random
import time
random.seed(1)
data = [random.randint(0, 10_000) for _ in range(3_000)]
def insertion_sort(items):
a = items[:]
for i in range(1, len(a)):
current, j = a[i], i - 1
while j >= 0 and a[j] > current:
a[j + 1] = a[j]
j -= 1
a[j + 1] = current
return a
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
timings = {}
for name, fn in [("insertion O(n^2)", insertion_sort), ("merge O(n log n)", merge_sort), ("built-in Timsort", sorted)]:
start = time.perf_counter()
result = fn(data)
timings[name] = time.perf_counter() - start
assert result == sorted(data)
fastest = min(timings, key=timings.get)
print("all results correct; fastest:", fastest)
print("insertion slower than merge:", timings["insertion O(n^2)"] > timings["merge O(n log n)"])
all results correct; fastest: built-in Timsort
insertion slower than merge: True
Common Mistakes
- Implementing your own sort in production code instead of using sorted()/list.sort().
- Forgetting that list.sort() sorts in place and returns None.
- Using the first element as quick sort's pivot on already-sorted data, causing O(n²).
- Assuming all sorts are stable — selection, quick and heap sort are not.
Exercise
Implement bubble sort as a function that returns a new sorted list. Then, using the built-in sorted, print the names of the people ordered by age and, for equal ages, by name.
Expected output: [1, 2, 5, 9] then ['Asha', 'Zoya', 'Ravi']
def bubble_sort(values):
items = list(values) # work on a copy
# TODO: repeatedly swap neighbouring items that are in the wrong order
return items
print(bubble_sort([5, 2, 9, 1]))
people = [("Ravi", 30), ("Zoya", 25), ("Asha", 25)]
# TODO: sort by age, then by name, and print just the names
Show hints
- Use two loops: the outer one counts the passes, the inner one compares
items[j]withitems[j + 1]and swaps them if needed. - A
keythat returns a tuple sorts by several fields:key=lambda person: (person[1], person[0]).
Show solution
def bubble_sort(values):
items = list(values) # work on a copy
for end in range(len(items) - 1, 0, -1):
for j in range(end):
if items[j] > items[j + 1]:
items[j], items[j + 1] = items[j + 1], items[j]
return items
print(bubble_sort([5, 2, 9, 1]))
people = [("Ravi", 30), ("Zoya", 25), ("Asha", 25)]
ordered = sorted(people, key=lambda person: (person[1], person[0]))
print([name for name, age in ordered])
Quick quiz
1. Which algorithm do sorted() and list.sort() use?
- A. Quick sort
- B. Heap sort
- C. Bubble sort
- D. Timsort
Show answer
D. Timsort is a hybrid of merge sort and insertion sort that is very fast on partly ordered data.
2. What does it mean that a sort is stable?
- A. Items that compare as equal keep their original order
- B. It never fails
- C. It uses no extra memory
- D. It always takes the same time
Show answer
A. Stability is what makes sorting by one field and then another work.
3. Which of these has the best worst-case running time?
- A. Bubble sort
- B. Merge sort
- C. Insertion sort
- D. Selection sort
Show answer
B. Merge sort is O(n log n) in every case; the other three are O(n²).
Interview questions
How do you sort a list of records by more than one field in Python?
Show answer
Give sorted a key that returns a tuple, for example key=lambda r: (r.department, r.name); tuples are compared element by element. When the directions differ, such as salary descending and name ascending, either negate the numeric field in the tuple, or sort twice, first by the secondary key and then by the primary one, which works because the sort is stable.
Why is quick sort O(n²) in the worst case, and how is that avoided?
Show answer
Quick sort splits the data around a pivot. If the pivot is always the smallest or largest item, as happens with a first-element pivot on sorted input, one side of each split is empty, giving n levels of work on n items. Choosing the pivot at random or as the median of three samples makes this very unlikely. Merge sort and Timsort avoid the problem entirely, which is one reason Python uses Timsort.
Key Points to Remember
- Bubble, selection and insertion sort are O(n²); insertion is fast on nearly sorted data.
- Merge, quick and heap sort are O(n log n) (quick sort on average).
- Python uses Timsort: stable, O(n log n) worst case, O(n) on sorted data.
- Stability enables multi-key sorting; tuple keys do it in one pass.
Practice in the playground
Write and run your own code for this topic, or start from the exercise or an example. Runs Python in your browser. Your code for each topic is kept in this browser.
Run the examples
Change an input, predict the result, then compare it with the output. Explain why the result changes.
Written by
WebNest Studio Engineering Team
Practical lessons from developers working with Java, Python, React, databases and production systems.
Led by Vansh Duggal, Founder, WebNest Studio · Full-stack & software engineering