- for Part 1, Thursday, October 20 or Monday, October 24, 2011, depending on the day of your lab;
- for Part 2, Thursday, October 27 or Monday, October 31, 2011, depending on the day of your lab.

**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).

A. For each of these five methods,

- write a
*regular*implementation in which the method simply returns the sorted array, and - write a
*pedagogical*implementation in which, every time we change an element of an array, the method shows the new state of the array and waits for the user to hit Return

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