8 Sorting and searching

If you keep proving stuff that others have done, getting confidence, increasing the complexities of your solutions---for the fun of it---then one day you'll turn around and discover that nobody actually did that one! And that's the way to become a computer scientist.
Richard Feynman, Lectures on Computation

This chapter presents two extended examples that use the programming techniques from Chapters 2-5 and analysis ideas from Chapters 6-7 to solve some interesting and important problems: sorting and searching. These examples involve some quite challenging problems and incorporate many of the ideas we have seen up to this point in the book. Once you understand them, you are well on your way to thinking like a computer scientist!