Write a merge Sort() method for the Sort able Linked List class from Section 8.5. As in Exercise 9.10, the original Sort able Linked List should be sorted when you are done. Your method must take time...

Write a merge Sort() method for the Sort able Linked List class from Section 8.5. As in Exercise 9.10, the original Sort able Linked List should be sorted when you are done. Your method must take time in Θ(n log n). (Hint: Look at the constructor from Go Fish (Figure 5–39) for an idea about dividing any list into two even halves. Make sure you deal with the case where the list being divided is of odd length.) Figure 5–39

Exercise 9.10

Write a merge Sort() method for the SortableArray List class from Section 8.4. Your method should invoke some kind of merge Sort Helper() to get a new, sorted list, but it should not simply return this result. Instead, it should copy the elements in this new list back into the original SortableArray List. How does this affect the running time of merge Sort()?