CPP 11
Merge-sort.cpp Guest on 5th April 2021 10:49:29 AM
  1. /*
  2.  * merge-sort.cpp
  3.  *
  4.  *  Created on: 23 Aug
  5.  *      Author: lucascordeiro
  6.  */
  7.  
  8. #include <iostream>
  9. #include <math.h>
  10. #include <limits.h>
  11. using namespace std;
  12.  
  13. void merge(int A[], int p, int q, int r)
  14. {
  15.     int i, j, k, n1, n2;
  16.     n1=q-p+1;
  17.     n2=r-q;
  18.     int  L[n1+1], R[n2+1];
  19.     for(i=0; i<n1; i++)
  20.         L[i]=A[p+i];
  21.     for(j=0; j<n2; j++)
  22.         R[j]=A[q+j+1];
  23.  
  24.     L[n1]=INT_MAX;
  25.     R[n2]=INT_MAX;
  26.     i=0;
  27.     j=0;
  28.     for(k=p; k<=r; k++)
  29.     {
  30.         if (L[i]<=R[j])
  31.         {
  32.             A[k]=L[i];
  33.             i++;
  34.         }
  35.         else
  36.         {
  37.             A[k]=R[j];
  38.             j++;
  39.         }
  40.     }
  41. }
  42.  
  43. void merge_sort(int A[], int p, int r)
  44. {
  45.   int q;
  46.   if (p<r)
  47.   {
  48.     q=ceil((p+r)/2);
  49.     merge_sort(A,p,q);
  50.     merge_sort(A,q+1,r);
  51.     merge(A,p,q,r);
  52.   }
  53. }
  54.  
  55. int main()
  56. {
  57.     int n=5;
  58.     int A[]={5,4,1,3,2};
  59. #if 1
  60.     cout << "before" << endl;
  61.     for(int i=0; i<n; i++)
  62.     {
  63.         cout << "A[" << i << "]=" << A[i] << endl;
  64.     }
  65. #endif
  66.     merge_sort(A,0,n-1);
  67. #if 1
  68.     cout << "after" << endl;
  69.     for(int i=0; i<n; i++)
  70.     {
  71.         cout << "A[" << i << "]=" << A[i] << endl;
  72.     }
  73. #endif
  74.     return 0;
  75. }

Paste-bin is for source code and general debugging text.

Login or Register to edit, delete and keep track of your pastes and more.

Raw Paste

Login or Register to edit or fork this paste. It's free.