Aim: - Implementation of Merge sort algorithm using Linked list as a data structure
Mergesort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two sub-collections and these are again sorted via merge sort. Once the two collections are sorted then the result is combined.
Conceptually, a merge sort works as follows
1. If the list is of length 0 or 1, then it is already sorted. Otherwise;
2. Divide the unsorted list into two sub-lists of about half the size.
3. Sort each sub-list recursively by re-applying merge sort.
4. Merge the two sub-lists back into one sorted list.
Example:- List (8,3,2,9,7,1,5,4)
Summary:- Merge sort is relatively a simple to code, fast, stable sorting routine with guaranteed O(n log n) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array