// Mergesort for a random permutation, see CLRS, 2nd ed
// Input:  Number of elements to generate for random permutation
//         and seed for srandom/random
// Output: Random integers in sorted order
// Simple recursive mergesort is used.  Several
// improvements could be made.

#include <stdio.h>
#include <math.h>

#define generateRandom(minRange,maxRange) \
  (minRange)+abs(random()) % ((maxRange)-(minRange)+1)

int *perm,permSize,numPerms;

void generatePerm()
// Uniform random permutation generator from CLRS
{
int i,k,temp;

for (i=0;i<permSize;i++)
  perm[i]=i;

for (i=0;i<permSize;i++)
{
  k=generateRandom(i,permSize-1);
  temp=perm[k];
  perm[k]=perm[i];
  perm[i]=temp;
}
}

void mergeSort(int *a,int N)
// a is an integer array with N elements that will be
// sorted back to a in ascending order.
{
int *left,leftSize,*right,rightSize;
int i,j,k;

if (N<=1)
  return; // Nothing to do
leftSize=N/2;
rightSize=N-leftSize;
// Temporary arrays for the two subproblems.
left=(int*) malloc(leftSize*sizeof(int));
right=(int*) malloc(rightSize*sizeof(int));
if (!left || !right)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}

// Copy the two pieces and sort.
for (i=0;i<leftSize;i++)
  left[i]=a[i];
for (i=0;i<rightSize;i++)
  right[i]=a[leftSize+i];
mergeSort(left,leftSize);
mergeSort(right,rightSize);

i=j=k=0; // index for left, index for right, and index for output
// Merge until one of the subarrays has been exhausted.
while (i<leftSize && j<rightSize)
  if (left[i]<=right[j])
    a[k++]=left[i++];
  else
    a[k++]=right[j++];
// Copy remainder of elements in the unexhausted array
if (i<leftSize)
  for ( ;i<leftSize;i++)
    a[k++]=left[i];
else
  for ( ;j<rightSize;j++)
    a[k++]=right[j];
free(left);
free(right);
}

main()
{
int seed;
int i,j;

printf("Enter permSize seed\n");
scanf("%d %d",&permSize,&seed);
perm=(int*) malloc(permSize*sizeof(int));
if (!perm)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}

srandom(seed);
generatePerm();
printf("Input: \n");
for (i=0;i<permSize;i++)
  printf("%d ",perm[i]);
printf("\n");

mergeSort(perm,permSize);
printf("Mergesort output: \n");
for (i=0;i<permSize;i++)
  printf("%d ",perm[i]);
printf("\n");

free(perm);
}