Question

Java Question:

Code the Merge Sort in such a way that it outputs the number of comparisons and the number of swaps performed when sorting a random set of items. Then use it to sort 1000, 5000, 10,000, and 100,000 integers. Tabulate the results and compare it to the number of comparisons and swaps calculated using the formulas given in Table 8.6.

Table 8.6 Performance of the Quicksort Algorithm Speed Memory Overhead Range Bytes lgorithm Range Effort Comments Binary Tree fas/slow high high 8 8" Fast for random data, Fast for random (n+1)|log("+1)-2】 < SE <-na-n2 slow for already sorted data. Highest overhead Babble very fast/slow Bubble very fast/slow lowest Fast for data almost sorted in ascending order. Slow for most data sets 0(n) , O(r') 0< Number of swaps< SE/2 Low overhead. Easy to code. SE <3mlog (n) Number of swaps·25E , 3 SE (0.75n)log Number of swaps 2.675E (" + 2) log(n-1)sSES㎡ Average = 1.45 nlog(n) Number of swaps 025SE Heap lowest4 fast O(rlog) fast Oinlogm Fast for all data sets Low overhead Merge Sort moderate 4m Fast for all data sets Moderate overhead Quicksort fast/slow low 8+8 Fastest for most data log sets, but could be (n-1 O(n for certain data sets. Easy to code Low overhead