Comparison of Sorts

In class, we discussed two quadratic sorting algorithms (Insertion-Sort and Selection-Sort) aswell as onenlgnsorting algorithm (Merge-Sort). Dozens, if not hundreds, of other sorting algo-rithms have been developed. Another well-known sorting algorithm isShellSortwhose asymp-totic running time is on the order ofnlg2n, when implemented appropriately.

In the problems that follow, you will compare these three algorithms for sorting. Ignoringlower order terms and constant factors, letT1(n),T2(n), andT3(n) be the "effort" required byInsertion/Selection-Sort, Shell-sort, and Merge-Sort, respectively, to sort a list of lengthn. We have:

T1(n) =n2

T2(n) =nlg2n

T3(n) =nlgn

where lgnis log2(n) and lg2n= (lgn)2

i.On asinglesheet of graph paper, plot the effort required by each of the these algorithmswhen run on lists of lengthn= 2, 4, 8, 16, and 32. For each algorithm, connect the plotpoints with a smooth, hand-drawn curve. See the plots given in the "Exponentials and Logs"appendix of the text for examples of what you should do. You may print a piece of graphpaper from the PDF located at the following URL:

https://www.printfreegraphpaper.com/gp/c-i-14.pdf

ii.Suppose that you were given a budget of 1,000 units of "effort." For each of the threealgorithms, determine the largest list length such that the sorting effort required is guaranteedto be at most 1,000.

iii.How many times larger is the list that Merge-Sort can handle, as compared to the lists thatInsertion/Selection-Sort and Shell-sort can handle? How many times larger is the list thatShell-sort can handle, as compared to the list that Insertion/Selection-Sort can handle?