// Stable, bottom-up mergesort for a random permutation, 
// see Sedgewick, 3rd ed, program 8.5

// 6/9/12 BPW

#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 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(b[j],a[i])) ? b[j++] : a[i++];
  }
}

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(b[j],a[i]))
      c[k++] = b[j++];
    else
      c[k++] = a[i++];

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

#define min(A,B) ((A<B) ? A:B)

void pass(Item outArr[], Item inArr[],int n, int m)
// inArr[] has n elements in ordered subarrays of m elements
// (last subarray may have n%m elements).
// outArr[] will end up with n elements in ordered subarrays of 2*m
// elements (last subarray may have n%(2*m) elements.
{
int i;

// Do merges as long as there is another pair of subarrays
// each with m elements
for (i=0; i<=n-m-m; i+=m+m)
  mergeAB(outArr+i, inArr+i, m, inArr+i+m, m);
// Process last one or two subarrays
if (i<n)
  mergeAB(outArr+i, inArr+i, min(m,n-i), inArr+i+m, min(m,n-m-i));
}

void mergesortABbu(Item a[], int n)
// Bottom-up mergesort using a work array
// Input and output use a[]
{
  int i,passes,m;
  Item *aux;

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

  // See Sedgewick Property 8.6
  for (passes=1;
       1<<passes < n;
       passes++)
    ;

  printf("%d passes are needed\n",passes);

  m=1;
  if (passes%2==1)
  { // If the number of passes is odd, then the first
    // pass must read from aux[] and write to a[]
    // Copy input to aux[]
    for (i = 0; i < n; i++)
      aux[i] = a[i];
    pass(a,aux,n,m);
    m=2;
  }

  while (m<n)
  { // Each iteration of this loop does two passes.
    pass(aux,a,n,m);
    m+=m;
    pass(a,aux,n,m);
    m+=m;
  }

  free(aux);
}

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");

mergesortABbu(a,n);
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);
}