Searching data involves determining whether a value (referred to as the search key) is present in the data and, if so, finding its location. Two popular search algorithms are the simple linear search and the faster but more complex binary search. Sorting places data in ascending or descending order, based on one or more sort keys. Your cell phone contacts list is sorted alphabetically, bank accounts are sorted by account number, employee payroll records are sorted by Social Security number, and so on. This chapter introduces two simple sorting algorithms, the selection sort and the insertion sort, along with the more efficient but more complex merge sort. The table below summarizes the searching and sorting algorithms, functions and methods discussed in the examples and exercises of this book.

The techniques in this chapter are provided to introduce students to the concepts behind searching and sorting algorithms—upper-level computer science courses typically discuss additional algorithms.