C++

Add a counter to the functions insertionSort and mergeSort that counts the number of comparisons that are made. Run two functions with arrays of various sizes. At what size does the difference in the number of comparisons between significant? How does this size that the orders of these algorithms predict? Compare your analysis with the actual running times and counter as a function of the input size n = 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 and clock() function.) Use the below code to generate an array value for testing.

for (int i = 0; i

{

//Create an unsorted array

arr[i] = (double)(n - i);

}

We need two tables for representing amount of comparison and running time.

output

INSERTION SORT Size: 2 Comparisons: 3 Running time is MERGE SORT Size: 2 Comparisons: 3 Running time is QUICK SORT Size: 2 Comparisons: 3 Running time is QUICK SORT 2 Size: 2 Comparisons: 4 Running time is e INSERTION SORT Size: 4 Comparisons: 15 Running time is MERGE SORT Size: 4 Comparisons: 7 Running time is e QUICK SORT Size: 4 Comparisons: 9 Running time is e QUICK SORT 2 Size: 4 Comparisons: 10 Running time is e INSERTION SORT Size: 8 Comparisons: 63 Running time is e MERGE SORT Size: 8 Comparisons: 15 Running time is QUICK SORT Size: 8 Comparisons: 24 Running time is e QUICK SORT 2 Size: 8 Comparisons: 25 Running time is INSERTION SORT Size: 16 MERGE SORT Size: 16 QUICK SORT Comparisons: 255 Running time is e Comparisons: 31 Running time is Size: 16 Comparisons: 61 Running time is e QUICK SORT 2 Size: 16 Comparisons: 62 Running time is e INSERTION SORT Size: 32 Comparisons: 1023 Running time is e MERGE SORT Size: 32 Comparisons: 63 Running time is e QUICK SORT Size: 32 Comparisons: 150 Running time is e QUICK SORT 2 Size: 32 Comparisons: 151 Running time is e INSERTION SORT Size: 2 Comparisons: 3 Running time is MERGE SORT Size: 2 Comparisons: 3 Running time is QUICK SORT Size: 2 Comparisons: 3 Running time is QUICK SORT 2 Size: 2 Comparisons: 4 Running time is e INSERTION SORT Size: 4 Comparisons: 15 Running time is MERGE SORT Size: 4 Comparisons: 7 Running time is e QUICK SORT Size: 4 Comparisons: 9 Running time is e QUICK SORT 2 Size: 4 Comparisons: 10 Running time is e INSERTION SORT Size: 8 Comparisons: 63 Running time is e MERGE SORT Size: 8 Comparisons: 15 Running time is QUICK SORT Size: 8 Comparisons: 24 Running time is e QUICK SORT 2 Size: 8 Comparisons: 25 Running time is INSERTION SORT Size: 16 MERGE SORT Size: 16 QUICK SORT Comparisons: 255 Running time is e Comparisons: 31 Running time is Size: 16 Comparisons: 61 Running time is e QUICK SORT 2 Size: 16 Comparisons: 62 Running time is e INSERTION SORT Size: 32 Comparisons: 1023 Running time is e MERGE SORT Size: 32 Comparisons: 63 Running time is e QUICK SORT Size: 32 Comparisons: 150 Running time is e QUICK SORT 2 Size: 32 Comparisons: 151 Running time is e