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 panic("not implemented"). The algorithms are described in prose and pseudocode in the next step. The test says whether you got them 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.

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 6.

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.