Sorting is what you do first so that everything after it gets easy. Watch one sort work honestly and slowly, then meet the idea that makes the real ones fast — the same idea from level two.
Sorting is rarely the point. It is what you do first, so that everything you want to do afterwards becomes easy — and it is the classic worked example of a problem with many correct answers of wildly different quality.
Remember level 6? Halving found a number in a list of eight billion in thirty-three looks, and it had one condition: the list had to be sorted. This level is that condition. Sort once, then search a thousand times cheaply — that trade is behind almost every fast thing a computer does.
Sixteen bars in a jumble. The method is the one you would invent yourself: look through what is left, find the smallest, swap it to the front. Then do it again with the rest.
Green is finished. Amber is being looked at. Lime is the smallest found so far.
Count what it just did. Sixteen bars took around 120 comparisons — because the first pass looks at 15, the next at 14, and so on all the way down.
That adds up faster than it feels. Double the list and you roughly quadruple the work, because you are doing twice as many passes and each pass is twice as long. A hundred items is about 5,000 comparisons. A thousand is about half a million. A million items would be five hundred billion, which is a computer thinking for days.
The sorts inside real software — the one behind sorting a column in a spreadsheet — are cleverer, and they use the trick from level 2: split the problem in half, sort each half, then merge them. That gets a million items done in roughly twenty million steps instead of five hundred billion. Same problem, same correct answer, twenty-five thousand times less work.
You are not expected to write that one yet. What matters now is that you can see why one is worse: not because it is written badly, but because of the shape of how its work grows.
One of you may only compare two cards at a time and swap them. The other counts every single comparison out loud. Do not stop counting.
Deal into two piles of eight. Each person sorts their own pile. Then merge the two sorted piles by repeatedly taking the smaller card off the front. Count again.
Round two wins, and it wins by more as the pack grows. The reason is level 2 wearing different clothes — you broke the problem in half, solved the halves, and combined them. That is not a sorting trick; it is the single most reusable idea in the whole subject, and you have now met it twice.
Twelve levels, no C++, nothing installed. You can break a problem apart until the pieces are obvious and name them; write steps precise enough for something with no judgment; read the three shapes every program is made of; trace values by hand to find where it goes wrong; recognise a problem you have already solved; say why one correct answer beats another; explain what a processor and a compiler actually do; read a number in binary and know why decimals are approximate; describe what a variable is and why the equals sign lies; fill in a truth table; and choose test values on purpose.
That is the semester CSCI-100 would have given you, and it is the thinking CSCI-135 says its lectures focus on. Everyone else in that room has done this. Now so have you — and unlike most of them, you did it recently.
Now the language. Setting up a Mac to compile C++ — and making sure what runs on your laptop also runs on the machines in the closed lab — is a genuinely fiddly afternoon that trips up more people in week one than any concept does. It is entirely solvable, and it is the next thing to build.
Order is an investment. You pay once so that everything after it gets cheap.
Watch the shape of the growth, not the speed on your laptop with ten items.
The same idea as level 2, and the most reusable one in the subject.
Not recall — these are the shapes an exam actually uses. Every answer below was produced by compiling and running the code, so if you disagree with one, the compiler is the one to believe.
Have a real go before revealing. Being wrong here is worth more than being right in three weeks.
Sorting 16 items by repeatedly finding the smallest takes how many comparisons? (15 + 14 + 13 …)
You double the list from 16 items to 32. Roughly what happens to the work?
Why sort a list at all, if you only want to find one thing in it?
← back to all 12 levels · stuck on anything? ask peter.