- for Part 1, Monday, July 30, 2012;
- for Part 2, Thursday, August 2, 2012.

**Objective:** The goal of this assignment is to practice
binary search trees and heapsort.

**Assignment:** Implement the following sorting methods:

- Part 1: place elements one by one into a balanced binary search tree, and then produce the elements in the increasing order (in-order);
- Part 2: perform heapsort.

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