Finding something in a messy list means checking items one by one. In a sorted list you can check the middle and throw away half — again and again. That's binary search.

Try it: press Search, then try a few new numbers.

Items	One by one (worst case)	Halving (worst case)
15	15	4
1,000	1,000	10
1,000,000	1,000,000	20

Sorting costs work up front and pays it back on every search. So how do we sort — and how much work does it take?