Write an in-place, linear-time algorithm that takes as input the linked list constructed by the Merge Sort 4 algorithm (Algorithm 7.4 ) and stores the records in the contiguous array slots in nondecreasing order according to the values of their keys using the Java language.

Algorithm 7.4 is attached.

I know this question ahs been asked before but answers were written in C/C++, could you do it in Java please?

void mergesort index low. index high index& merge dlist) index mid. list1. list high){ merged list low; SI merged list link 0: t else mid L(low high )/2J mergesort (low, mid, list1); mergesort (mid 1 high. list?) merge 4 list2 merge dlist) (list1 void merges (index list1 index list2, index& merged list) index last sorted; if (S list 11.key SI list2].key){ //Find the start of the merged list merged ist list1: listi SI list 11. link else merged list list? list? SI list21. link lastsorted merged list while (list 1 0 && liste 0) if SIlist11.key SI list 21. key /Attach smaller key to merged list Sllastsortedl. link list 1: last sorted list list SI list link 11. else SIlast sortedl. link list 2; last sorted list? list2 SI list 21. link After one list ends, if (list1 S last sorted. link list2 attach remainder of the else other. SI last sorted]. link list1