The implementation for Mergesort given in Section 7.4 takes an array as input and sorts that array. At the beginning of Section 7.4 there is a simple pseudocode implementation for sorting a linked list using Mergesort. Implement both a linked list-based version of Mergesort and the array-based version of Mergesort, and compare their running times.

Transcribed Image Text:

7.4 Mergesort A natural approach to problem solving is divide and conquer. In terms of sorting, we might consider breaking the list to be sorted into pieces, process the pieces, and then put them back together somehow. A simple way to do this would be to split the list in half, sort the halves, and then merge the sorted halves together. This is the idea behind Mergesort. Mergesort is one of the simplest sorting algorithms conceptually, and has good performance both in the asymptotic sense and in empirical running time. Supris- ingly, even though it is based on a simple concept, it is relatively difficult to im- plement in practice. Figure 7.7 illustrates Mergesort. A pseudocode sketch of Mergesort is as follows: List mergesort (List inlist) { from inlist; if (inlist.length()