Sorting and Searching

reading · we frame, you read MIT or the canonical taught · we author, no canonical fits ↺ spirals back to earlier lessons

Course locked

Complete Graph Fundamentals first.

This course unlocks once you've finished its prerequisite. Open prerequisite →

Prerequisites

Introduction to Algorithms and Complexity not yet

Linear Data Structures not yet

Complete prerequisites first to enroll.

reading · 35 min + ~240 min canonical

The Sorting Family Tree: Bubble to Quicksort, and What They All Trade

Sorting is the first algorithm you learned, probably in some loop-with-swaps form, and it's the algorithm with more named variants than any other. Bubble, selection, insertion, me…

primary UC Berkeley CS61B — Sorting sections

preview →

reading · 30 min + ~240 min canonical L1

The Ω(n log n) Lower Bound: Why No Comparison Sort Can Beat It

You've now seen at least six sorting algorithms. Three are O(n²). Three are O(n log n). The natural question is: can we do better than O(n log n)? Is there some sufficiently cleve…

primary UC Berkeley CS61B — Sorting sections

after L1 locked

reading · 30 min + ~240 min canonical L1

Non-Comparison Sorting: Counting, Radix, and How to Beat O(n log n) by Cheating

You just proved no comparison sort can beat Ω(n log n). The natural follow-up question is: what if we don't use comparisons? It turns out that for restricted inputs — integers in …

primary UC Berkeley CS61B — Sorting sections

after L2 locked

reading · 30 min + ~240 min canonical L1

Binary Search and Its Many Disguises: From Sorted Arrays to "Search on Answer"

Binary search is the algorithm you learned in week one — given a sorted array, find a target in O(log n) by halving the search space repeatedly. That's the standard form. The inte…

primary UC Berkeley CS61B — Sorting sections

after L3 locked

reading · 35 min + ~240 min canonical L1

Order Statistics and Quickselect: Finding the K-th Element Without Sorting

You want the median of a billion numbers. The obvious algorithm: sort them and take the middle one. O(n log n). For a billion items, that's hours. Now consider — you don't need th…

primary UC Berkeley CS61B — Sorting sections

after L4 locked

exercise reading · 15 min L1

Exercises: Easy (Warm-up)

- [ ] Binary Search (#704) — NC/LC — Classic binary search on sorted array - [ ] Best Time to Buy and Sell Stock (#121) — NC/LC — Track min price, max profit in one pass - [ ] Imp…

after L5 locked

exercise reading · 30 min L1

Exercises: Medium (Core)

- [ ] Search a 2D Matrix (#74) — NC/LC — Binary search treating 2D as 1D - [ ] Koko Eating Bananas (#875) — NC/LC — Binary search on answer space - [ ] Find Minimum in Rotated Sor…

after L6 locked

exercise reading · 45 min L1

Exercises: Hard (Stretch)

- [ ] Median of Two Sorted Arrays (#4) — NC/LC — Binary search on partition, O(log(min(m,n))) - [ ] Implement radix sort for integers in Ruby — Non-comparison O(nk) sort - [ ] Cou…

after L7 locked

exercise reading · 60 min L1

Mini-Project

- [ ] Build a sorting visualizer in Ruby — terminal-based visualization of bubble, merge, and quicksort using ASCII bars; show comparisons, swaps, and step count in real time

after L8 locked

L10

project reading · 360 min L1

Project: Sorting Algorithm Benchmark Suite

Implement 7 sorting algorithms in Ruby (bubble, selection, insertion, merge, quick, heap, radix) with a uniform interface. Benchmark all of them on random, sorted, reverse-sorted,…

after L9 locked

L11

assessment reading · 70 min L1

Self-Assessment: Sorting and Searching

- [ ] Explain merge sort. What is its time and space complexity? Is it stable? - [ ] Explain quicksort. What makes a good pivot? What is quicksort's worst case and how do you avoi…

after L10 locked

11 lessons. Read in order; spiral back when you need to. By the end you'll have used the core ideas twice — once on the abstract, once on something you'll meet at work next week.