Mergesort

 Mergesort

• Merge sort is a recursive algorithm based on Divide-and-Conquer. The algorithm divides the unsorted list into n sublists, recursively, until all sublists are of length one, which is considered already sorted.
• The algorithm compares and repeatedly merge sublists to produce sorted sublists by calling the merge function, this is done until the sorted sublists merge into one final sorted list.
• Merge sort is preferred over quick sort when there is a large dataset, and/or stored in external storage.

Example:

•  The merge sort procedure recursively divides the unsorted list into sublists of equal halves in a top-down manner, until sublists of length one. As the list recursively divides, the original order of the list is preserved. In the case of odd length, the list is divided into sublists of near-equal size, using round functions.

            Input List:     [7, 6, 5, 4, 3, 2, 1]

                                      /               \

                           [7, 6, 5, 4]         [3, 2, 1]

                               /      \               /      \

                        [7, 6]      [5, 4]    [3, 2]   [1]

                           /  \          /  \        /  \

                       [7]  [6]    [5]  [4]  [3]  [2]  [1]

• In a bottom-up manner, the merge procedure recursively compares and copies individual elements from each list and merge them into another list, placing all the elements in a sorted order. The resulting list requires extra resources and memory.

         [7]  [6]  [5]  [4]  [3]  [2]  [1]

           \   /    \   /   \    /      \

            \ /       \  /    \ /        \

         [6, 7]     [4, 5]    [2, 3]        [1]

                 \      /             \      /

              [4, 5, 6, 7]         [1, 2, 3]

                          \              /

Output List:    [1, 2, 3, 4, 5, 6, 7]

• The runtime of merge sort is given by the formula, T(n) = 2*T(n/2) + n, where T(n) is the number of comparisons required to sort a list containing n elements. The algorithm, repeatly, reduces the problem size by half (n/2) each time it splits the unsorted list of numbers into two sublists. Each sublist can be sorted in T(n/2). Additionally, n comparisons are performed when merging the two sublists together.

Advantages of Merge Sort

1. It is stable sorting method.
2. It is very efficient.
3. It can be applied to files of any size.
4. It is quicker for larger lists because unlike insertion and bubble sort is cloesn't go thorgh the whole list serval times.

Disadvantages of Meger Sort

1. Additional memory is required for the merging process.
2. It is not in-place method.
3. slower comparative to the other sort algorithms for smaller task.
4. Merge sort require more space than other sort.

Data structure: Array

Worst-case time complexity: O(nlogn)

Average-case time complexity: O(nlogn)

Best-case time complexity:  Ω(nlogn)

Space complexity: O(n)                                                                                                                                        

CODE:

👇

1. #include<stdio.h>
2. void merge(int a[], int low ,int high);
3. void mergesort(int a[], int low ,int mid  ,int high);
4. int comp_cnt,swap_cnt;
5. void main()
6. {
7.     int i,a[20],n;
8.     printf("how many elements you want to enter:-");
9.     scanf("%d",&n);
10.     printf("enter %d elements: ",n);
11.      for(i=0; i<n; i++)
12.         scanf("%d",&a[i]);
13.         merge(a,0,n-1);
14.         printf("shorted elements is: \t  \n");
15.         for(i=0;i<n;i++)
16.             printf("%d\t",a[i]);
17. }
18. 
    
19. void mergesort(int a[], int low ,int mid  ,int high)
20. {
21. int i=low,j=mid+1,k=0,b[20];           
22.         comp_cnt++;
23.         while((i<=mid)&&(j<=high))
24.        {
25.              comp_cnt++;  
26.              if(a[i]<a[j])
27.            {
28.                 swap_cnt++;
29.                 b[k++]=a[i++];
30.    }
31.            else
32.           {
33.                 swap_cnt++;
34.                 b[k++]=a[j++];
35.           }
36.       }
37.     comp_cnt++;
38.     while(i<=mid)
39.     {
40.         swap_cnt++;
41.         b[k++]=a[i++];
42.     }
43.     comp_cnt++;
44.     while(j<=high)
45.     {
46.         swap_cnt++;
47.         b[k++]=a[j++];
48.     }
49.     for(j=low, k=0; j<=high;  j++,k++)
50.     {
51.         swap_cnt++;
52.         a[j]=b[k];
53.     }
54. }
55. 
    
56. void merge(int a[],int low ,int high)
57. {
58.     int mid;
59.     comp_cnt++;
60.     if(low<high)
61.     {
62.     mid=(low+high)/2;
63. merge(a,low,mid);
64.         merge(a,mid+1,high);
65.   mergesort(a,low,mid,high);
66.     }
67. 
    
68.  }

👉Execute👈

//Output

/*

how many elements you want to enter:-5

enter 5 elements: 47

84

9

42

16

shorted elements is:   

9 16 42 47 84

*/

                                                                     //ThE ProFessoR