SkyHawk

Merge Sort

Jul 6th, 2011
467
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <limits.h>
  2. void merge(int* a,int la,int lb);
  3.  
  4. void mergeSort(int* p,int l)
  5. {
  6.     if(l<=1)
  7.         return;
  8.     int q = l>>1;
  9.     mergeSort(p,q);
  10.     mergeSort(p+q,l-q);
  11.     merge(p,q,l-q);
  12. }
  13.  
  14. void merge(int* a,int la,int lb)
  15. {
  16.     int* a1 = new int[la+1];
  17.     int* b1 = new int[lb+1];
  18.     for(int i = 0;i<la;++i)
  19.         a1[i] = a[i];
  20.     int* b = a+la;
  21.     for(int i = 0;i<lb;++i)
  22.         b1[i] = b[i];
  23.     a1[la] = INT_MAX;
  24.     b1[lb] = INT_MAX;
  25.     int p = 0, q = 0;
  26.     for(int i = 0;i<la+lb;++i)
  27.         if(a1[p]<=b1[q])
  28.             a[i] = a1[p++];
  29.         else
  30.             a[i] = b1[q++];
  31.     delete a1;
  32.     delete b1;
  33. }
RAW Paste Data