/* Parallel Mergesort.    C.W. Kessler 10/97
 * sorts N elements using p processors, synchronous version.
 * Assumes that all elements are different;
 * otherwise the result will be wrong.
 */

#include <fork.h>
#include <assert.h>
#include <io.h>
#include <stdlib.h>

sh int N;   /* number of array elements */
sh int *a;  /* the array to be sorted */

#define THRESHOLD 1

sh simple_lock screen = 0;  /*screen output is a critical section*/

/* print an array a of size n sequentially
 */
void print_array( int *a, int n )
{
 int i;
 simple_lockup( &screen );
  pprintf("Array %p of size %d:\n", a, n);
  for (i=0; i<n; i++) printf(" %d", a[i]);
  printf("\n");
 simple_unlock( &screen );
}


/* sequential sorting, using bubble sort.
 * Assumes that outarray is allocated.
 */
void seq_sort( int *array, int n, int *outarray )
{
 int i,j;
 int temp;
 for (i=0; i<n; i++) outarray[i] = array[i];
 for (i=0; i<n-1; i++)
   for (j=i+1; j<n; j++)
     if (outarray[i] > outarray[j]) {  /*swap:*/
       temp = outarray[i];
       outarray[i] = outarray[j];
       outarray[j] = temp;
     }
}


/* in sequential compute the rank of key within
 * array of size n, i.e. # array-elements < key
 */
int get_rank( int key, int *array, int n )
{
 int left = 0;
 int right = n-1;
 int mid;
 if (key >= array[n-1]) return n;
 if (key == array[n-1]) return n-1;
 if (key <= array[0]) return 0;
 while (left < right-1) {   /*binary search*/
    /*always maintain array[left] <= key < array[right]*/
    mid = (right+left)/2;
    if (key < array[mid]) right = mid;
    else                  left = mid;
 }
 if (key==array[left]) return left;
 else                  return left+1;
}
 

/* merge array src1 of size n1 and src2 of size n2
 * into one array dest of size n1+n2. 
 * Assertions: p>1, n1*n2>=1, dest array is allocated.
 */
sync void merge( int *src1, int n1, int *src2, int n2, int *dest)
{
 sh int p = groupsize();
 sh int iter;
 sh int *rank12, *rank21;  /*temp. rank arrays*/
 pr int i;
 farm assert(p>1);
 rank12 = (int *)shalloc( n1 );
 rank21 = (int *)shalloc( n2 );
 farm pprintf(" merge( src1=%p, n1=%d, src2=%p, n2=%d, dest=%p, n=%d, p=%d)\n",
           src1,n1,src2,n2,dest,n1+n2,p);
 iter = 0;
 farm
   /* self-scheduling par. loop over rank computations: */
   for (i=mpadd(&iter,1); i<n1; i=mpadd(&iter,1)) 
     rank12[i] = get_rank( src1[i], src2, n2 ); 
 iter = 0;
 farm
   for (i=mpadd(&iter,1); i<n2; i=mpadd(&iter,1)) 
     rank21[i] = get_rank( src2[i], src1, n1 ); 
 farm {
   /* copy elements to dest using the rank information */
   for (i=$; i<n1; i+=p)  dest[i+rank12[i]] = src1[i];
   for (i=$; i<n2; i+=p)  dest[i+rank21[i]] = src2[i];
 }
}


/* mergesort for an array of size n.
 * The sorted array is to be stored in
 * sortedarray which is assumed to be allocated.
 */
sync void mergesort( int *array, int n, int *sortedarray )
{
 sh int p = groupsize();

 seq pprintf(" mergesort( array=%p, n=%d, p=%d)\n", array,n,p);

 if (n<=THRESHOLD || p==1)
     /*ignore warning: n and p are equal for all callers of this group */
     seq seq_sort( array, n, sortedarray );
 else {
    sh int *temp = (int *)shalloc( n );
    fork (2; @=$%2; $=$/2)
       mergesort( array + @*(n/2), (1-@)*(n/2) + @*(n-n/2), temp + @*(n/2) );
    merge( temp, n/2, temp+n/2, n-n/2, sortedarray );
 }
}


void main( void )
{
 pr int j;
 if ($==0) {
    prS("Enter N = ");
    scanf("%d", &N);
 }
 srand( 8*$*$*$ + 4*$*$ - 18*$ + 37 );
 start {
   sh int *b;
   a = (int *) shalloc( N );
   b = (int *) shalloc( N );
   farm for (j=$; j<N; j+=__STARTED_PROCS__)  a[j] = rand()%8192; /*set array*/
   seq print_array( a, N );
   mergesort( a, N, b ); 
   seq print_array( b, N );
 }
 barrier; 
 simple_lockup( &screen );
   printAccStat();
 simple_unlock( &screen );
 barrier; 
 exit(0);
}