Using the class _DoublyLinkedBase from page 274 of lecture 8 notes as the linked list implementation, implement mergesort on a doubly linked list.
Your mergesort function should accept an instance of type _DoublyLinkedBase, which you will construct in main by repeatedly inserting random numbers into a _DoublyLinkedBase instance.
Once you have verified that your sorting algorithm is correct, test the algorithm on a range of list sizes from 10 to 1000 in increments of 10 (n=10, n=20, n=30, n=40, … , n=1000).
Finally, implement merge sort in python that handles a python List (array type) as input, instead of doubly linked list (can use my implementation on moodle). Compare the sorting times for mergesort on the _DoublyLinkedBase vs the List implementation. Use python’s matplotlib plotting function to generate a plot similar to what you see below, comparing mergesort on a _DoublyLinkedBase to mergesort on a List:
*note – the above plot compares quicksort and mergesort, from input sizes of 1 to 100,000. You will show something similar, but compare linked _DoublyLinkedBase mergesort to List mergesort on input sizes of 10 to 1000.
Include your plot as a pdf file along with your source code. Comment on the efficiency of linked list vs array implementation. Which is faster? Why?
