Sorting Algorithms

Sorting is the classic proving ground for algorithmic thinking. You will almost always call Python's built-in sorted() in real code, but implementing the classics teaches you divide and conquer, in-place manipulation, and complexity analysis in the most concrete way possible. Interviewers love sorting because it reveals whether you understand why an algorithm is fast, not just that it is.

What You'll Learn

• Bubble sort and insertion sort: the O(n^2) baselines
• Merge sort: divide and conquer at O(n log n)
• How quicksort partitions around a pivot
• What Python's own Timsort does and how to use sorted() like a pro

Bubble Sort: The Teaching Baseline

Repeatedly sweep the list, swapping adjacent pairs that are out of order. Each sweep bubbles the largest remaining value to the end. Two nested passes over the data: O(n^2).

Insertion Sort: Great When Nearly Sorted

Take each element and slide it left into its place among the already-sorted prefix, like sorting cards in your hand. Still O(n^2) worst case, but O(n) on nearly-sorted data, which is why real libraries use it for small chunks:

Merge Sort: Divide and Conquer

Split the list in half, sort each half recursively (recursion from last lesson!), then merge the two sorted halves. The merge is O(n), the halving gives O(log n) levels, so the total is O(n log n), guaranteed, on any input:

The merge step is the heart: two sorted lists zip together in one pass by always taking the smaller front element.

Quicksort: Partition Around a Pivot

Pick a pivot, split the rest into smaller-than and larger-than groups, sort each recursively. Average O(n log n) and very fast in practice; a consistently bad pivot degrades it to O(n^2):

Race Them

Time the classics against each other and against the built-in. Open fullscreen and try bigger sizes:

Sorting Like a Python Pro

In production you use sorted() (returns a new list) or list.sort() (in place). Both run Timsort, a hybrid of merge sort and insertion sort that exploits already-sorted runs, worst case O(n log n) and stable. The real skill is the key parameter:

Exercises

Key Takeaways

• Bubble and insertion sort are O(n^2); insertion sort wins on nearly-sorted data
• Merge sort guarantees O(n log n) by splitting, recursing, and merging in one pass
• Quicksort partitions around a pivot: O(n log n) average, fast in practice
• Python's sorted() is Timsort: stable, O(n log n), and the right choice in real code
• Master the key parameter (including tuple keys) for real-world sorting tasks