- for Part 1, Friday, July 13, 2012;
- for Part 2, Tuesday, July 17, 2012.

**Objective:** The goal of this assignment is to practice
sorting.

**Assignment:** Implement the following sorting methods
described in the book:

- selection sort, bubble sort, and insertion sort (Part 1);
- mergesort and quicksort (Part 2).

For each of these five methods, use techniques described in Assignment 3 to record the computation time needed for each sorting method; for sizes n = 100, 200, 300, and 400 run each several times (e.g., 100) with a randomly generated array and record, for each of the methods, how the average running time grows as a function of n. Explain, to the TA, how the dependence of running time on the array size compares with the estimates of the running time given in the book.