You need to analyze your code for various test cases and provide a the analysis for the following experiments in the report. You need to add the functions in timing.cpp file to report for the experiments:

$1.$ Compare the time complexity of the insertion sort with three different input cases. Generate first

vector with random integers of various sizes $($already provided in the timing cpp file$).$ Follow the

instructions in timing.cpp to generate enough data points to observe a trend. Generate second vector

with sorted integers of various sizes. Generate third vector with reverse sorted integers of various sizes.

The size set you are using should be same for all $3$ cases. Find the time taken by the algorithms for

the three cases of input. Plot a graph with x$-$axis label indicating varying input size of the vector

and y$-$axis label the experimental time $($in seconds$)$ reported by your implementation. There should

be three curve lines each corresponding to the three different input cases. Describe your observations

from the plot and what inference statement you can derive about the results.

$2.$ Compare the time complexity of the traditional merge sort $($when k $=1)$ with three different input

cases. Generate first vector with random integers of various sizes $($already provided in the timing

cpp file$).$ Generate second vector with sorted integers of various sizes. Generate third vector with

reverse sorted integers of various sizes. Find the time taken by the algorithms for the three cases of

input. Plot a graph with x$-$axis label indicating varying input size of the vector and y$-$axis label the

experimental time $($in seconds$)$ reported by your implementation. There should be three curve lines

each corresponding to the three different input cases. Describe your observations from the plot and

what inference statement you can derive about the results.

$3.$ Compare the time complexity of the merge sort algorithm on different value of k$.$ Generate a vector

with random integers of various sizes. Choose three different values of k: $24$

$($already provided in the

timing cpp file$),2$

$6$

$,2$

$8$

$.$ Plot a graph with x$-$axis label indicating varying input size of the vector$($and

list$)$ and y$-$axis label the experimental time $($in seconds$)$ reported by your implementation. There

should be $4$ curves corresponding to three k values and traditional merge sort $($with k $=1).$ Describe

your observations from the #include

#include

#include

#include

#include

#include

#include

#include "sort.h$"$

using namespace std;

using namespace chrono;

$///$ @todo Modify timing.cpp to evaluate the various sorting algorithms on the

$///$ following input types:

$///-$ Random sequence

$///-$ Sorted sequence

$///-$ Reverse sorted sequence$///$ @brief Generate random sequence and insetion$\_$sort

$///$ @param k merge sort sub$-$problem size $($not used$)$

$///$ @param sz Vector size

duration insertion$\_$sort$\_$random$\_$sequence$\_$k$($size$\_$t sz$,$ size$\_$t k$)\{$

vector v;

for$($size$\_$t i $=0$; i $<$ sz; $++$i$)$

v$.$push$\_$back$($rand$())$;

$//$ create a clock

high$\_$resolution$\_$clock::time$\_$point start $=$ high$\_$resolution$\_$clock::now$()$;

my$\_$algorithm::insertion$\_$sort$($v$.$begin$(),$ v$.$end$(),$ less$())$;

$//$ calculate time

high$\_$resolution$\_$clock::time$\_$point stop $=$ high$\_$resolution$\_$clock::now$()$;

duration diff $=$ d$///$ @brief Generate random sequence and sort

$///$ @param k merge sort sub$-$problem size

$///$ @param sz vector size

duration merge$\_$sort$\_$random$\_$sequence$\_$k$($size$\_$t sz$,$ size$\_$t k$)\{$

vector v;

for$($size$\_$t i $=0$; i $<$ sz; $++$i$)$

v$.$push$\_$back$($rand$())$;

$//$ create a clock

high$\_$resolution$\_$clock::time$\_$point start $=$ high$\_$resolution$\_$clock::now$()$;

my$\_$algorithm::merge$\_$sort$($v$.$begin$(),$ v$.$end$(),$ less$(),$ k$)$;

$//$ calculate time

high$\_$resolution$\_$clock::time$\_$point stop $=$ high$\_$resolution$\_$clock::now$()$;

duration diff $=$ duration$\_$cast$>($stop $-$ start$)$;

return diff;

$\}$

$///$ @brief Control timing of single function

template

void time$\_$function$($Func f$,$ size$\_$t max$\_$size, size$\_$t k$,$ string name$)\{$

cout $<<$ "Function: $"<<$ name $<<$ endl;

cout $<<$ setw$(15)<<$ "Size" $<<$ setw$(15)<<$ "Time$($sec$)"<<$ endl;

$//$ control input size

for$($size$\_$t i $=2$; i $<$ max$\_$size; i$*=2)\{$

cout $<<$ setw$(15)<<$ i;

duration diff$(0\mathrm{.}0)$;

$//$ loop a specific number of times to make the clock tick

size$\_$t num$\_$itr $=$ max$($size$\_$t$(10),$ max$\_$size $/$ i$)$;

for$($size$\_$t j $=0$; j $<$ num$\_$itr; $++$j$)$

diff $+=$ f$($i$,$ k$)$;

cout $<<$ setw$(15)<<$ diff.count$()/$ num$\_$itr $<<$ endl;

$\}$

$\}$

$///$ @brief Main function to time all your functions

int main$()\{$

time$\_$function$($insertion$\_$sort$\_$random$\_$sequence$\_$k$,$ pow$(2,17),1,$ "Insertion Sort Random Sequence"$)$;

time$\_$function$($merge$\_$sort$\_$random$\_$sequence$\_$k$,$ pow$(2,23),1,$ "Merge Sort $($traditional$)$ Random Sequence"$)$;

time$\_$function$($merge$\_$sort$\_$random$\_$sequence$\_$k$,$ pow$(2,23),$ pow$(2,4),$ "Merge Sort Random Sequence $2^4$ k$")$;

$///$ @TODO $-$ Add more function calls based on report

$\}$