Sorting Algorithms — Core Concepts

Why sorting matters in practice

Every time you filter search results, display a leaderboard, or find the median of a dataset, sorting is doing the heavy lifting underneath. Understanding how sorting works lets you pick the right tool, avoid performance traps, and write code that scales.

Python’s built-in sorted() and list.sort() are excellent defaults. But knowing what happens inside them — and what alternatives exist — makes you a stronger developer.

The main families of sorting

Comparison-based sorts

These decide order by comparing pairs of elements.

• Bubble Sort — repeatedly swap adjacent elements that are out of order. Easy to understand, terrible at scale. Runs in O(n²) time on average.
• Selection Sort — scan the unsorted portion, find the minimum, place it at the front. Also O(n²), but does fewer swaps than bubble sort.
• Insertion Sort — build a sorted section one element at a time by sliding each new element into place. Fast for small or nearly-sorted lists. O(n²) worst case, but O(n) when data is already almost sorted.
• Merge Sort — divide the list in half, sort each half recursively, then merge. Guaranteed O(n log n) time, but uses extra memory for the temporary merged list.
• Quick Sort — pick a “pivot,” partition elements around it, then recurse on each side. Average O(n log n), but O(n²) in the worst case if the pivot is poorly chosen.

Non-comparison sorts

These exploit the structure of the data itself.

• Counting Sort — count how many times each value appears, then reconstruct. O(n + k) where k is the range of values. Only works with integers in a limited range.
• Radix Sort — sort digit by digit, from least significant to most significant. O(d × n) where d is the number of digits. Great for fixed-length integers or strings.

How Python’s Timsort works

Python uses Timsort (named after Tim Peters). It is a hybrid of merge sort and insertion sort designed for real-world data:

1. Scan the list for “runs” — sequences that are already ascending or descending.
2. Short runs get extended to a minimum length using insertion sort.
3. Runs are merged together using a modified merge sort with a temporary buffer.

Timsort excels on partially sorted data, which is surprisingly common in practice. Its worst case is O(n log n) and it is stable — equal elements keep their original order.

Stability: why it matters

A stable sort preserves the relative order of items that compare as equal. This matters when you sort by multiple criteria. For example, if you sort employees first by department, then stable-sort by salary, employees within the same salary keep their department grouping.

Python’s sorted() and list.sort() are both stable.

Choosing the right approach

Situation	Best choice
General purpose	sorted() / list.sort() (Timsort)
Nearly sorted data	Timsort handles this automatically
Small lists (< 20 items)	Insertion sort (Timsort uses this internally)
Integers in a known range	Counting sort
Fixed-length strings or IDs	Radix sort
Need guaranteed O(n log n) and low memory	Heap sort (not common in Python)

Common misconception

“Quick sort is always the fastest.” Quick sort has great average-case performance, but its O(n²) worst case can be triggered by sorted or nearly-sorted input — exactly the kind of data that Timsort handles best. In Python, the built-in sort beats a hand-written quick sort almost every time.

Custom sorting with key functions

Python lets you control sort order with a key parameter:

words = ["banana", "apple", "cherry"]
sorted(words, key=len)  # ['apple', 'banana', 'cherry']

The key function is called once per element, and Timsort sorts by the resulting values. This is faster than using a comparison function because each element is transformed only once.

One thing to remember: Python’s built-in sort is almost always your best option. Learn how it works so you know when the rare exceptions apply — and reach for custom sorting only when the data structure demands it.