Choosing the Right Algorithm

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 5 Time to complete: ~20 minutes

Full Comparison Table
Python's Built-In Sort: Timsort
A Decision Guide
Try It Yourself
Summary & Next Steps

1. Full Comparison Table

Algorithm	Best	Average	Worst	Space	Stable?	In-Place?
Bubble Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes	Yes
Selection Sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	No	Yes
Insertion Sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes	Yes
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes	No
Quick Sort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`*	No	Yes

* Quick sort's O(log n) space is for the recursion stack on average; a poor pivot choice can push this toward O(n) in the worst case, alongside its O(n²) time.

2. Python's Built-In Sort: Timsort

Python's sorted() and list.sort() use Timsort, a hybrid algorithm that:

Uses insertion sort (Chapter 3) on small sub-arrays, where its low overhead beats more complex algorithms.
Uses a merge-sort-like strategy (Chapter 4) to combine larger sorted runs, guaranteeing O(n log n) worst case.
Detects and takes advantage of already-sorted "runs" in real-world data, often performing better than O(n log n) on partially-sorted input.
Is stable — a deliberate design choice, since Python users frequently sort by one key while relying on original order for ties.

items = [5, 2, 8, 1, 9]
sorted(items)              # returns a NEW sorted list, O(n log n), stable
items.sort()                 # sorts IN PLACE, same guarantees
items.sort(key=lambda x: -x)  # custom sort key, e.g. descending order

In practice, you almost never hand-write a sort in production Python — this whole module exists to build the intuition needed to reason about algorithms, including ones like Timsort that you'll only ever call, not implement.

3. A Decision Guide

Data is tiny (roughly under ~20 elements) → insertion sort's low constant overhead often wins; this is exactly why Timsort uses it internally for small runs.
Data is nearly sorted already → insertion sort's near-O(n) best case shines.
You need a guarantee, no matter the input (e.g., a public API, unknown adversarial input) → merge sort's O(n log n) worst case is safer than quick sort's O(n²) worst case.
You need to minimize memory use and can tolerate rare worst-case slowness → quick sort's in-place O(log n) space beats merge sort's O(n).
Stability matters (sorting by one field, preserving order on ties) → merge sort or Python's built-in sorted(), never quick sort or selection sort.
You're writing real Python code, not implementing a sort from scratch for learning → just use sorted() / .sort() — Timsort already made these tradeoffs for you.

4. Try It Yourself

For each scenario, name the best-fit algorithm and justify it in one sentence:

(a) Sorting a list of 8 employee records by department, and employees with the
    same department must keep their original relative order.

(b) Sorting a huge, mostly-already-sorted log file where only a handful of new
    entries were appended at random positions.

(c) Sorting user-submitted data in a public API where you must guarantee
    performance even against adversarially-crafted worst-case input.

Answers (click to expand)

(a) Insertion sort (or merge sort) — stability is required, and 8 elements is small enough that insertion sort's simplicity wins; merge sort is the more general stable choice for larger data.
(b) Insertion sort — nearly-sorted data means very little shifting is needed, giving near-O(n) real-world performance. (This is also precisely the scenario Timsort is designed to detect and exploit automatically.)
(c) Merge sort — its O(n log n) worst case can't be forced into O(n²) the way quick sort's can with adversarial input, which matters when you don't control what data arrives.

5. Summary & Next Steps

Key Takeaways

No single sorting algorithm is best in every situation — the right choice depends on data size, existing order, stability needs, and worst-case guarantees.
Merge sort trades memory for a guaranteed O(n log n) worst case; quick sort trades a rare O(n²) worst case for in-place sorting.
Python's built-in Timsort is a hybrid of insertion sort (for small runs) and merge sort (for combining runs), and it's what you should actually use in real code.
This module's five algorithms were about building the reasoning skills to make (or explain) this kind of tradeoff — not about replacing sorted().

Concept Check

Why does quick sort's in-place property come at the cost of a worst-case time guarantee, while merge sort trades the opposite way?
Why does Timsort use insertion sort internally for small sub-arrays instead of merge sort or quick sort?
If you needed to sort a list of transactions by amount, but transactions with equal amounts must stay in their original (chronological) order, which algorithm(s) from this module would you rule out, and why?

Next Module

→ Module 4: Recursion & Backtracking

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index