Advertisement
Tariqul_Islam

Merge sort

Jul 30th, 2019
276
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.27 KB | None | 0 0
  1. #include<stdlib.h>
  2. #include<stdio.h>
  3.  
  4. void merge(int arr[], int l, int c, int r)
  5. {
  6.     int i, j, k;
  7.     int n1 = c - l + 1;
  8.     int n2 =  r - c;
  9.  
  10.     int L[n1], R[n2];
  11.  
  12.     for (i = 0; i < n1; i++)
  13.       {
  14.             L[i] = arr[l + i];
  15.       }
  16.     for (j = 0; j < n2; j++)
  17.       {
  18.             R[j] = arr[c + 1+ j];
  19.       }
  20.  
  21.  
  22.     i = 0;
  23.     j = 0;
  24.     k = l;
  25.     while (i < n1 && j < n2)
  26.     {
  27.         if (L[i] <= R[j])
  28.         {
  29.             arr[k] = L[i];
  30.             i++;
  31.         }
  32.         else
  33.         {
  34.             arr[k] = R[j];
  35.             j++;
  36.         }
  37.         k++;
  38.     }
  39.  
  40.     while (i < n1)
  41.     {
  42.         arr[k] = L[i];
  43.         i++;
  44.         k++;
  45.     }
  46.  
  47.     while (j < n2)
  48.     {
  49.         arr[k] = R[j];
  50.         j++;
  51.         k++;
  52.     }
  53. }
  54. void mergeSort(int arr[], int l, int r)
  55. {
  56.     if (l < r)
  57.     {
  58.         int c = (l+r)/2;
  59.  
  60.         mergeSort(arr, l, c);
  61.         mergeSort(arr, c+1, r);
  62.  
  63.         merge(arr, l, c, r);
  64.     }
  65. }
  66.  
  67. int main()
  68. {
  69.     int n,i;
  70.     scanf("%d",&n);
  71.     int arr[n];
  72.     for(i=0;i<n;i++)
  73.     {
  74.         scanf("%d",&arr[i]);
  75.     }
  76.  
  77.     mergeSort(arr, 0, n-1);
  78.  
  79.     printf("\nSorted array is \n");
  80.     for(i=0;i<n;i++)
  81.     {
  82.         printf("%d ",arr[i]);
  83.     }
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement