Merge Sort

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