Problem:
Question- Create a program to perform a merge sort on a linked list.
Specification:
- Create a linked list of 100 random integers in the range 1-1000.
- Display the unsorted linked list in a 10 x 10 table.
- To sort the linked list using a merge sort routine:
- Convert the linked list to an array.
- Perform a recursive merge sort on the array.
Change the merge sort algorithm to use a non-recursive algorithm (selection sort, insertion sort) when the size of the partitions is below some threshold.
Insert a comment in the merge sort routine that explains how you decided what the threshold would be.
Once the sort is complete, convert the array back into a linked list.
Display the sorted linked list in a 10 x 10 table.