The textbook's Sorts.java merge() method creates a temporary array as part of merging, which is wasteful of computer memory. An alternative would be to store data to be sorted in a linked list rather than an array and to merge "in place" within the list. That is, the merge would be implemented by removing nodes from one part of the list and adding them to another part. Your assignment is to implement such a merge in the mergelist() method of the attached class MergeSortList.java. If your method is implemented properly, running the main method of MergeSortList should output a sorted list of numbers (the original version compiles and executes but outputs an unsorted list). Hints: Your new method should be similar in some ways to the merge() method contained in Sorts.java, with the major difference being that the new method will not use a temporary array. Instead, it should use the add(int index, E element) and remove(int index) methods of java.util.LinkedList to remove a node from one part of the list and add its info to a new node in another part of the list. Note also that the get(index i) method of LinkedList allows you to access elements of a LinkedList in much the same way you can access elements of an array using [i] notation. You'll need to be careful with how you update your method's indices (the mid, i2, and i3 variables from merge(); you won't need i1, since that indexed into the temporary array that you won't be using). Also, think carefully about what to do once one of the two lists being merged is empty; it might be easier to handle this than you would at first think!

Attachment:- MergeSortList.java.zip