Sorting experiments In this assignment, you will implement 5 different sorting algorithms and test their performance on different types of input.

Algorithms: Insertion sort Shell sort Mergesort Quicksort Radix sort std::sort (on std::vector, it is already implemented in )

Input types Pre-sorted array from 1..N Reverse-sorted array from N..1 Random array with few duplicates (use rand()%N) Array with many duplicates (use rand()%10) Array of all duplicates (all zeros)

For each type of input array, test on 5 different sizes: N=100, N=1000, N=10000, N=100000, N=1000000 Results: Provide the results of your sorting experiments in 5 separate tables (one for each input size) as follow:

	Pre-sorted	Reverse-sorted	Rand%N	Rand%10	Zeros
Insertiondsort
Shell sort
Merge sort
Quick sort
Radix sort
std::sort

Discuss and justify your results. Which algorithm performs best overall (when averaging across all input sizes and input types)? Be sure to mention time complexity when discussing your results. Also, be sure to used std::move whenever possible in your c++ implementations, and test in release mode.

Submit your c++ source code as well as a pdf containing your name, the required tables (5x) and your discussion of the results. if an algorithm takes > 2 minutes on any of the input sizes, you can stop the algorithm and write >2min in the table.

improving your sorting algorithms Use insertion sort on the divided sub-arrays of merge sort once they get below a certain size o This speeds up merge sort because it removes the need for copying elements into new arrays, which adds a lot of overhead to the running time Use a random pivot for quicksort to improve its running time on the pre-sorted and reverse-sorted arrays Try different gap sequences for shell sort

ANSWER NEEDED: C++ CODE AND THE REQUIRED TABLES