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

**Assignment:** Implement all four sorting methods described
in the book: insertion sort, shell sort, merge sort, and quick sort.

For each of these 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

**For extra credit:** Use techniques described in Assignment 3 to
record the computation time needed for
each sorting method; for sizes n = 10, 20, 30, and 40
run each several times (e.g., 100) with a randomly generated array and
record, for each of the four methods,
how the average running time grows as a function of n.