Answer Happy

Write an in-place, linear-time algorithm that takes as input the
linked list constructed by the Mergesort 4 algorithm (Algorithm
7.4) and stores the records in the contiguous array slots in
non-decreasing order according to the values of their keys.
Algorithm 7.4 Mergesort 4 (Linked Version) Problem: Sort n keys in nondecreasing order. Inputs: positive integer n; array of records, S, of the type just given, indexed from 1 to n. Outputs: the array S with the values in the key field sorted in nondecreasing order. The records are in an ordered linked list using the link field. void mergesort4 (index low, index high, index& mergedlist) { index mid, listi, list2; if (low high) { mergedlist = low; S[ mergedlist]. link = 0; } else{ mid l(low + high)/2]; mergesort4(low, mid, list1); mergesort4 (mid + 1, high, list2); merge4(list1, list2 , mergedlist); } void merge4 (index listi, index list2, index& mergedlist) { index lastsorted;
7.4 MERGESORT REVISITED 301 if (S[list1]. key < mergedlist list1 = S[list1]. link; S[list2).key){ // Find the start of the merged list. list1; else{ mergedlist = list 2; list 2 = S[list2]. link; lastsorted = mergedlist; while (list1 != 0 && list2 != 0) if S[list1]. key <S[list2]. key{//Attach smaller key to merged list. S[lastsorted]. link = list1; lastsorted = list1; list1 = S[list1]. link; else{ S[lastsorted). link = list2; lastsorted = list 2; list2 = S

• . link; == if (list 1 0) S[lastsorted]. link = list2; else S[lastsorted]. link = list1; // After one list ends, // attach remainder of the // other }