The fourth question of lesson 6's homework asked what one sort costs, and how many binary searches it takes to pay for it.

That is why this lesson exists. Binary search needs sorted data, and you cannot sort yet — until now you have used sort.Slice without knowing what is inside.

From this lesson you sort it yourself.

What changes from here

Until now the right-hand panel showed you the whole file, and that was the lesson.

From this lesson it shows a skeleton: the package, the imports, the signatures, the contracts, and whatever you are missing. The test says whether you got it right.

The reason is simple: until now the code was the tool you learned with. From here the code is the exercise. Showing it would be handing over the answer.

The lesson climbs in steps

You do not have to start from a blank panic("not implemented"). Each algorithm arrives in three rungs, and the lesson climbs them in order:

1. Watch. Five numbers, three algorithms, every move written in a table. You write nothing.
2. Fill the holes. Insertion sort arrives with its loops already written. Two lines are missing.
3. Write it yourself. Bubble sort and selection sort — empty skeletons.

The next lessons follow the same path, with higher rungs.

Three algorithms, one complexity class

All three algorithms in this lesson are O(n²). All three are "bad" in the sense textbooks use the word.

And one of them is nevertheless a component of Go's standard library sort — step 8.

Best, average, worst — now three numbers

Lesson 1 defined the three cases and measured them for linear search. In sorting they become far sharper, because the order of the input changes the amount of work by a factor of hundreds.

algo gen is already prepared for this. In lesson 1 you wrote the -sorted and -reverse flags, and the text said they would pay off three times. This is the first of the three.

Guess before you read on

Three algorithms — bubble sort, selection sort and insertion sort. All O(n²).

Write down two things:

1. Which of the three is fastest on 10,000 randomly scattered items?
2. Which is fastest if the data is already nearly sorted?

The second answer is not the same as the first. And it differs by more than you expect.