Two Sorts Worth Understanding
You will almost never write a sort in production. You will constantly reason about them in interviews and when debugging performance. So learn two algorithms cold, then trust the standard library for everything else.
Merge sort splits the array in half, sorts each half, and merges them back in order. It is the poster child for divide-and-conquer.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
It is O(n log n) always, no bad cases. The cost is O(n) extra memory for the merge buffers. Because it never reorders equal elements, it is stable ā a property that matters more than beginners expect.
Quicksort picks a pivot, partitions everything smaller to the left and larger to the right, then recurses on each side. Average O(n log n), and it sorts in place with tiny constants, which is why it wins real benchmarks. Its dirty secret: a bad pivot on already-sorted data degrades to O(nĀ²). Production quicksorts dodge this by choosing the pivot randomly or with median-of-three. When an interviewer asks "what's the worst case," they want to hear O(nĀ²) and the fix.
The comparison you should memorize: merge sort trades memory for a guarantee; quicksort trades a guarantee for speed and locality.
Timsort: What sorted() Actually Runs
Python's sorted() and list.sort() do not run either of the above. They run Timsort, a hybrid of merge sort and insertion sort designed for data that is already partly ordered ā which real data usually is.
Timsort scans for "runs" of already-sorted elements, extends short runs with insertion sort, then merges the runs like merge sort. On sorted or nearly-sorted input it approaches O(n); worst case stays O(n log n). It is stable, so sorting by one key then another gives you predictable multi-level ordering.
That stability is a tool. To sort records by last name, then break ties by first name, sort by the least significant key first:
people.sort(key=lambda p: p.first_name)
people.sort(key=lambda p: p.last_name) # ties keep first-name order
Two rules that will save you interview time. First, sorted() returns a new list; .sort() mutates in place and returns None ā never write x = mylist.sort(). Second, always sort with a key function, never a cmp. Want descending? Pass reverse=True. Want to sort by multiple fields at once? Return a tuple: key=lambda p: (p.age, p.name). Tuples compare left to right, which handles tie-breaking for free.
If you want to go deeper on Python idioms like these, the Advanced Python Programming course covers keys, comparators, and the data model in detail.
Binary Search on Arrays
Once data is sorted, you can find anything in O(log n) by halving the search space each step. The logic is trivial and the bugs are legendary ā off-by-ones live here.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Three details decide whether your binary search is correct: the loop condition (<= when hi is a valid index), how you move the bounds (mid + 1 and mid - 1, never leave them unchanged or you loop forever), and what you return when the target is missing.
Do not hand-roll this when you do not have to. Python's bisect module is a tested binary search on any sorted list:
import bisect
i = bisect.bisect_left(scores, 90) # first index where 90 could go
bisect.insort(scores, 90) # insert while keeping sorted order
bisect_left gives you the leftmost insertion point, bisect_right the rightmost. Together they answer "how many values are below X," "does X exist," and "what is the next-largest value" without a loop in sight.
Binary Search on Answers
Here is the pattern that separates people who know binary search from people who can use it. Binary search does not need an array. It needs a monotonic yes/no question: something that is false, false, false, then true, true, true. You binary-search the boundary.
Classic setup: "What is the minimum ship capacity to deliver all packages in D days?" Bigger capacity is always feasible, smaller is not ā monotonic. So search the capacity range.
def min_capacity(weights, days):
def feasible(cap):
need, load = 1, 0
for w in weights:
if load + w > cap:
need += 1
load = 0
load += w
return need <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
You never sorted anything. You defined a feasible predicate, confirmed it flips exactly once as the answer grows, and searched the value range. The tell that a problem wants this: it asks for a minimum or maximum, the search space is a range of numbers, and checking one candidate is cheap.
Your working checklist for any sorting-or-searching problem: if you need order, call sorted() and trust Timsort. If you need to look something up repeatedly in ordered data, reach for bisect. If a problem asks for the smallest or largest value satisfying some condition, stop scanning linearly and ask whether the condition is monotonic ā if it is, you just turned an O(n) or O(nĀ²) search into O(log n) over the answer space. That reflex is worth more than memorizing any single sort.