SkyHawk

Merge Sort (Optimised)

Jul 6th, 2011
367
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <limits.h>
  2. #include "sort.hpp"
  3. void mergeopt(int* a,int la,int lb);
  4. void mergeoptSort1(int* p,int l);
  5.  
  6. int* mem;
  7. int pos = 0;
  8.  
  9. void mergeoptSort(int* p,int l)
  10. {
  11.     mem = new int[l+2];
  12.     mergeoptSort1(p,l);
  13. }
  14.  
  15. void mergeoptSort1(int* p,int l)
  16. {
  17.     if(l<=1)
  18.         return;
  19.     if(l<=20)
  20.     {
  21.         inSort(p,l);
  22.         return;
  23.     }
  24.     int q = l>>1;
  25.     mergeoptSort1(p,q);
  26.     mergeoptSort1(p+q,l-q);
  27.     mergeopt(p,q,l-q);
  28. }
  29.  
  30. inline int* alloc(int l)
  31. {
  32.     int* res = mem + pos;
  33.     pos+=l;
  34.     return res;
  35. }
  36.  
  37. inline void de_alloc(int l)
  38. {
  39.     pos -= l;
  40. }
  41.  
  42. void mergeopt(int* a,int la,int lb)
  43. {
  44.     int* a1 = alloc(la+1);
  45.     int* b1 = alloc(lb+1);
  46.     for(int i = 0;i<la;++i)
  47.         a1[i] = a[i];
  48.     int* b = a+la;
  49.     for(int i = 0;i<lb;++i)
  50.         b1[i] = b[i];
  51.     a1[la] = INT_MAX;
  52.     b1[lb] = INT_MAX;
  53.     int p = 0, q = 0;
  54.     int t = la+lb;
  55.     for(int i = 0;i<t;++i)
  56.         if(a1[p]<=b1[q])
  57.             a[i] = a1[p++];
  58.         else
  59.             a[i] = b1[q++];
  60.     de_alloc(la+1);
  61.     de_alloc(lb+1);
  62. }
RAW Paste Data