Sorting algorithms are good examples for studying algorithm design and analysis. Sorting is a classic subject in computer science. There are three reasons to study sorting algorithms.

• First, sorting algorithms illustrate many creative approaches to problem solving, and these approaches can be applied to solve other problems.
• Second, sorting algorithms are good for practicing fundamental programming techniques using selection statements, loops, methods, and arrays.
• Third, sorting algorithms are excellent examples to demonstrate algorithm performance.

The data to be sorted might be integers, doubles, characters, or objects. Section, Sorting Arrays, presented selection sort. The selection sort algorithm was extended to sort an array of objects in Section, Case Study: Sorting an Array of Objects. The Java API contains several overloaded sort methods for sorting primitive type values and objects in the java.util.Arrays and java.util.Collections classes. For simplicity, this chapter assumes:

1. data to be sorted are integers,
2. data are stored in an array, and
3. data are sorted in ascending order.

The programs can be easily modified to sort other types of data, to sort in descending order, or to sort data in an ArrayList or a LinkedList.

There are many algorithms for sorting. You have already learned selection sort. This chapter introduces insertion sort, bubble sort, merge sort, quick sort, bucket sort, radix sort, and external sort.