6.10.B IMPLEMENT MERGESORT PROGRAM

1. Algorithm Merge sort(low, high)
2. //a[low: high] is a global array to be sorted
3. //small (p) is true if there if there is only one element
4. //to sort in this case the list is already sorted
5. {
6. if(low7. {
8. //divide p into sub problems
9. //find where to split the set
10. mid:=[(low+ high)/2];
11. //solve the sub problems
12. Merge sort (low, mid);
13. Merge sort (mid+1, high);
14. //combines the solutions
15. Merge (low, mid, high);
16. }
17. }

ALGORITHM FOR MERGINGTWO SORTED SUB ARRAYS

1. Algorithm Merge (low, mid, high)
2. //a[low: high] is a global array containing
3. //two sorted subsets in a
4. //[low: mid] and in a[mid+1, high]. The global
5. //is to merge these two sets into a single
6. //set residing in a[low: high] b[] is a
7. // Auxiliary global array
8. {
9. h:=low; i:=low; j:=mid+1;
10. while((h<=mid) and (j<=high)) do
11. {
12. if(a[h]<=a[j]) then
13. {
14. b[i]: = a[h]; h:=h+1;
15. }
16. else

Merge Sort relies on the merge function to merge together two sorted arrays. Merge Sort gets its efficiency from the fact that at most one comparison is needed for each item being merged. Think about merging two decks of cards, A and B, into a third deck C. Decks A and B are assumed to each be already in sorted order. Deck C stars out empty. You compare the top cards from each deck and place the smaller of the two, face down, on the merged deck. When either deck A or deck B becomes empty, you place the entire remaining deck, face down, onto deck C. The key here is that the two decks, A and B are sorted to begin with. At most one comparison is made for each card merged. When one of the decks becomes empty, no further comparisons are done and the entire remining deck is merged in at once. This is the basis for the following merge algorithm. In this algorithm, the "cards" are stored in an array. Deck A is stored in indices low1..high1, inclusive. Deck B is stored in indices low2..high2. We further stipulate that the two "decks" are contiguous in the array (the last card of deck A comes just before the first card of deck B). The mergesort algorithm uses the merge algorithm (below) to sort the entire array. To sort the whole array A, low would be zero and high would be the maximum index in the array.
Sample input and output
Output for merge sort
enter size of list:6
enter the unsorted elements:3
2
1
5
4
6
elements in list are 3 2 1 5 4 6
merge sorted list is 1 2 3 4 5 6