C++

In this project you will implement all the sorting algorithms that we studied in chapter 7, namely, Insertion sort, Selection sort, Exchange sort, Merge sort, Heap sort and Radix sort. Each sorting algorithm should be implemented as a function. The sorting algorithms should be called from the main function.

You should run the code using different kinds of lists, namely, a list sorted in increasing order, a list sorted in decreasing order, and a random list. You can use the built in random number generator to generate the random list.

For Insertion sort, Selection sort, Exchange sort, Merge sort and Heap sort, your code should count how many comparisons are made by each method to sort a list of integers.

To implement Radix sort you will assume that the numbers are in base 10 (decimal) and you would need to use 10 piles to represent each decimal digit. Each pile can be represented using a linked list. To study the performance of Radix sort you should use the built in time function to calculate how much time is spent sorting each type of list.

Deliverables: 1) Your C++ code. 2) The output, which should specify how many comparisons are made for each value of n for Insertion sort, selection sort, Exchange sort, merge sort and heap sort. Use the following values of n for the list size: 100, 10,000, 100,000, 250,000, 500,000. For Radix sort, the output should specify the amount of time spent sorting each type of list for each value of n.