Sunday, December 5, 2010

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

No comments:

Post a Comment