Given a list L[0:n - 1], one way of maintaining a sorted order of L is to use an auxiliary array Link[0:n - 1].

The array Link[0:n - 1] serves as a linked list determining the next highest element in L, so the elements of L can be given in nondecreasing order by

L[Start], L[Link[Start]], L[Link[Link[Start]]], and so forth. Then Linkn-1[Start] is the index of the largest element in L, and we set Link[Linkn-1[Start]] = Linkn[Start] = 0 to signal the end of the linked list.

Design a version of MergeSort that uses the auxiliary array Link.

Attachment:- Given a list L.zip