# This exercise walks you through an implementation of the merge-sort algorithm for sorting a DLList,…

This exercise walks you through an implementation of the merge-sort algorithm for sorting a DLList, as discussed in Section.

1. Write a DLList method called take First(12). This method takes the first node from 12 and appends it to the the receiving list. This is equivalent to add(size(),12.remove(0)), except that it should not create a new node.

2. Write a DLList static method, merge(11,12), that takes two sorted lists 11 and 12, merges them, and returns a new sorted list containing the result. This causes 11 and 12 to be emptied in the proces.

3. Write a DLList method sort() that sorts the elements contained in the list using the merge sort algorithm. This recursive algorithm works in the following way:

(a)    If the list contains 0 or 1 elements then there is nothing to do. Otherwise,

(b)   Using the truncate(size()/2) method, split the list into two lists of approximately equal length, 11 and 12;

(c)    Recursively sort 11;

(d)   Recursively sort 12; and, finally,

(e)    Merge 11 and 12 into a single sorted list.

The next few exercises are more advanced and require a clear understanding of what happens to the minimum value stored in a Stack or Queue as items are added and removed.