*[Homework 5 is due on Aug 5 at 11:59pm]*

**Problem**: [*Sorting contest*] Choose and implement *any three* sorting algorithms (working on an array of integers), with one selection taken from each group presented below, and establish empirically which is the best sorting algorithm among them (in terms of time taken to sort large arrays).

**Group 1** [Worst case complexity: Θ(n^{2})]

- Selection Sort
- Insertion Sort

**Group 2** [Worst case complexity: Θ(n log n)]

- Heapsort
- Mergesort
- Splay tree sort

**Group 3** [Worst case complexity: Θ(n^{2}); Average case complexity: Θ(n log n)]

- Quicksort (with randomized or median-of-3 pivot selection)

The starter files are here. Things that are left for you:

1. Implement *three* of the chosen sorting algorithms. The corresponding header files are already there. For example, if you choose to implement Merge Sort, your implementation should go into MergeSort.h. I have already provided the implementations of Exchange Sort in ExchangeSort.h and BST Sort in BSTSort.h as samples.

2.** [Already provided]** Introduce a time check wrapper around the call to each sorting algorithm. In order to further simplify your work, I have modified main.cpp to have the timing wrappers.

3. **[Bonus]** (a) Vary the inputs and come up with a graphical comparison between the chosen sorting algorithms. (b) Also, for fun, feel free to add a poor quality pivot selection (with first element chosen as the pivot) in Quicksort to see the result. To accomplish this, you can add another file called PoorQuickSort.h, where PoorQuickSort will inherit from SortingAlgorithm. In main.cpp, add the necessary instantiation of PoorQuickSort and timing wrappers.

Write a short report on your finding and submit that along with the source code changes.

**Expected output**: If implemented properly, you should get the following trend of numbers.

—————————————-

TIME TAKEN BY VARIOUS SORTING ALGORITHMS

—————————————-

Exchange Sort: 35376

Heap Sort: 909

Insertion Sort: 12385

Merge Sort: 578

Quick Sort: 358

Poor Quick Sort: 5963

Selection Sort: 10809

Binary Search Tree Sort: 15691

Splay Tree Sort: 272

**Solution**:

The solution files are here.