Phase 4: Computational Thinking & Algorithms · ~35 minutes · Python · uv

Sorting

A hand-written sort that works perfectly on already-sorted input can still be completely broken. Testing only the easy case is how that bug survives.

Hiring signal: Uses the battle-tested built-in sort in real code, and knows exactly why that's the correct choice, not a shortcut

What you will learn

Implement insertion sort by hand and trace how it builds a sorted result incrementally
Use Python's built-in sorted() with a custom key, and explain why it's the right real-world choice
Diagnose a real correctness bug in a hand-written sort that only shows up on specific inputs
Distinguish a correctness bug from a performance problem

Introduction

Type: Learn Languages: Python Prerequisites: Lesson 02 (Big-O Intuition) Time: ~35 minutes

Objective

Learning objectives

Implement insertion sort by hand and trace how it builds a sorted result incrementally
Use Python's built-in sorted() with a custom key, and explain why it's the right real-world choice
Diagnose a real correctness bug in a hand-written sort that only shows up on specific inputs
Distinguish a correctness bug from a performance problem

What you're building

A script (sort_verification.py) that:

Implements insertion_sort correctly, as shown above
Verifies it against sorted() on at least 6 test cases, including empty, single-item, already-sorted, reverse-sorted, and duplicate-containing lists
Contains a deliberately introduced bug of your own invention (not the exact j > 0 one from this lesson) in a second version, along with a comment identifying which specific test case exposes it and why
Uses sorted(..., key=...) on a list of dictionaries (your own data) to sort by a field other than the default order

You need to sort a list of strings by length, shortest first, and break ties alphabetically for strings of the same length. Which call is correct?

key=len alone sorts by length only — same-length words end up in whatever order they originally were in (Timsort is stable, but that's not the same as alphabetical). key=lambda w: (len(w), w) returns a tuple for each word; Python compares tuples element by element, so this sorts by length first, and for equal lengths, falls through to comparing the strings themselves alphabetically — exactly the two-level ordering asked for. The other two options aren't valid Python for this task (reverse expects True/False, not a function; .sort() modifies in place and returns None, so chaining it after sorted() doesn't work as written).

Unlock the full lesson

You've read the first 2 sections. The rest of this lesson covers The Problem, Check Yourself, Key Terms & Next — plus a hands-on lab, quiz, and project artifact.

Create a free account to unlock Phase 0 and Phase 1 of every course — no credit card.