// Mergesort for a random permutation, see Sedgewick, 3rd ed.
// Not stable, but merge and insertion sort routines could easily be changed.

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

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

typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)

void generatePerm(int *perm,int permSize)
{
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 insertion(Item a[], int ell, int r)
// Unstable insertion sort
{
int i;
// Put minimum value at left end of subarray
for (i = ell+1; i <= r; i++)
  compexch(a[ell], a[i]);
for (i = ell+2; i <= r; i++)
{
  int j = i;
  Item v = a[i];
  while (less(v, a[j-1]))
  {
    a[j] = a[j-1];
    j--;
  }
  a[j] = v;
}
}

void mergeABsedgewick(Item c[], Item a[], int N, Item b[], int M )
{ int i, j, k;
  for (i = 0, j = 0, k = 0; k < N+M; k++)
  {
    if (i == N) { c[k] = b[j++]; continue; }
    if (j == M) { c[k] = a[i++]; continue; }
    c[k] = (less(a[i], b[j])) ? a[i++] : b[j++];
  }
}

void mergeAB(Item c[], Item a[], int N, Item b[], int M )
// Merges arrays a[] and b[] into array c[]
{
  int i = 0, j = 0, k = 0;

  while (i < N && j < M)
    if (less(a[i],b[j]))
      c[k++] = a[i++];
    else
      c[k++] = b[j++];

  if (i < N)
    for ( ; i < N; i++)
      c[k++] = a[i];
  else
    for ( ; j < M; j++)
      c[k++] = b[j];
}

void mergesortABr(Item a[], Item b[], int ell, int r)
// Takes unsorted b[ell] through b[r] and returns ordered
// in a[ell] through b[r].
{
  int m = (ell+r)/2;  // First m elements of subarray are sorted together
  if (r-ell <= 10)
  { // Avoid recursion overhead
    insertion(a, ell, r);
    return;
  }
  // Recursively sort the two subarrays
  mergesortABr(b, a, ell, m);  
  mergesortABr(b, a, m+1, r);
  // Merge the ordered results
  mergeAB(a+ell, b+ell, m-ell+1, b+m+1, r-m);
}

void mergesortAB(Item a[], int ell, int r)
// Sorts a[] between a[ell] and a[r]
{
  int i;
  Item *aux;

  aux=(int*) malloc(r*sizeof(int));
  if (!aux)
  {
    printf("malloc failed %d\n",__LINE__);
    exit(0);
  }

  // Copying is necessary for many input cases to assure
  // that base case for recursion works correctly.
  for (i = ell; i <= r; i++)
    aux[i] = a[i];
  mergesortABr(a, aux, ell, r);
}

int main()
{
int seed,n;
int i;
int *a;

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

srandom(seed);
generatePerm(a,n);
printf("Input: \n");
for (i=0;i<n;i++)
{
  printf("%d ",a[i]);
  if (i%10==9)
    printf("\n");
}
if (n%10!=0)
  printf("\n");

mergesortAB(a,0,n-1);
printf("Mergesort output: \n");
for (i=0;i<n;i++)
{
  printf("%d ",a[i]);
  if (i%10==9)
    printf("\n");
}
if (n%10!=0)
  printf("\n");

free(a);
}