4_106.cilk

#include <iostream>
#include <cstdlib>
#include <cilk.h>
#include <cilkview.h>
#define N 1000000

using namespace std;
#define MAXM(a,b) (a)>(b)?(a):(b)
int binarySearch( int value, int a[], int l, int r );
void merge( int t[], int a[], int p1, int r1, int p2, int r2, int p3 );
void mergesort(int arr[],int sorted[], int l, int h, int ind)
{
	int n = h-l+1;
	int merged[n];
	int m = (l+h)/2;
	if(n<1)return;
	if(n==1)
	{
		
		sorted[ind] = arr[l];
		return;
	}
	
	int q = h-l+1;
	
	cilk_spawn mergesort(arr,merged, l, m,0);
	
	mergesort(arr,merged, m+1,h,m-l+1);

	cilk_sync;	

	merge(merged,sorted,0,m-l,m-l+1,n-1,ind);
	
}

int binarySearch( int value, int a[], int l, int r )
{
    long low=l;
    long high = l>(r+1)?l:(r+1);
   
    while(low<high)
    {
        long mid = (low +high)/2;
        if (value<=a[mid]) high =mid;
        else  low= mid+1; 
    }
    return high;
}

void merge( int t[], int a[], int p1, int r1, int p2, int r2, int p3 )
{
  
    int l1=r1-p1+1;
    int l2=r2-p2+1;
    if (l1<l2)
    {
        merge(t,a,p2,r2,p1,r1,p3);
	return;
  }
    
    if (l1==0) return;
    int q1 =(p1+r1)/2;
    int q2 = binarySearch(t[q1],t,p2,r2);
    int q3 = p3+(q1-p1)+(q2-p2);
    a[q3] = t[q1];
    cilk_spawn merge(t,a,p1,q1-1,p2,q2-1,p3);
    merge(t,a,q1+1,r1,q2,r2,q3+1);
    cilk_sync;
}



int cilk_main()
{
	int arr[N];
	int sorted[N];
	srand(time(0));
	for(int i=0;i<N;i++)
	{
		arr[i]=rand()%300;
		sorted[i]=0;
	}
//out<<endl;
	int num;
	cilk::cilkview cv;
	cv.reset();
        cv.start();
	mergesort(arr,sorted,0, N-1,0);

	cv.stop();
        cv.dump("dump-pmerge06");
#ifdef PRINT	
	
	for(int i=0;i<N;i++)
		cout<<arr[i]<<" ";
	cout<<endl;

	for(int i=0;i<N;i++)
		cout<<sorted[i]<<" ";
	cout<<endl;
#endif
}