Sorting Linked Lists
In this homework you will implement mergesort and quicksort on doubly linked lists. It is important that you do not create new nodes in the list when sorting. Instead, you should rearrange the nodes using the convenience methods provided in the SortableDLL class. The linked list already has one node per item and the sorting does not change this.
Implement these two sorting methods in a subclass of the SortableDLL class called MySortableDLL . The methods should modify the list rather than producing a new one. If L is a MySortableDLL object then the following code should sort it.
L.quicksort()
L.mergesort()
You may add parameters to these methods, but you will have to give them default values so that the code above works.
Beware certain pitfalls: Use an iterator at your own peril. Modifying a linked list while iterating through it is very tricky and prone to errors.