// Mergesort
#include <stdio.h>
#include <stdlib.h>

int merge(int *in1,int *in2,int *out1,int in1Size,int in2Size)
// Merge (union with duplicates) for two ordered tables in1 and in2
// to give out1.
{
int i,j,k;

i=j=k=0;
while (i<in1Size && j<in2Size)
  if (in1[i]<in2[j])
    out1[k++]=in1[i++];
  else
    out1[k++]=in2[j++];
if (i<in1Size)
  for ( ;i<in1Size;i++)
    out1[k++]=in1[i];
else
  for ( ;j<in2Size;j++)
    out1[k++]=in2[j];
return k;
}

void mymergesort(int *arr,int *work,int n)
{
int nleft,nright,i;

if (n<2)
  return;
nleft=n/2;
nright=n-nleft;
for (i=0;i<n;i++)
  work[i]=arr[i];
mymergesort(work,arr,nleft);
mymergesort(work+nleft,arr+nleft,nright); // pointer arithmetic
merge(work,work+nleft,arr,nleft,nright); // pointer arithmetic
}

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

scanf("%d %d",&n,&seed);
srandom(seed);
a=(int*) malloc(n*sizeof(int));
work=(int*) malloc(n*sizeof(int));
if (!a || !work)
{
  printf("malloc failed\n");
  exit(0);
}
for (i=0;i<n;i++)
  a[i]=labs(random())%1000;
printf("input:\n");
for (i=0;i<n;i++)
  printf("%d %d\n",i,a[i]);
mymergesort(a,work,n);
printf("output:\n");
for (i=0;i<n;i++)
  printf("%d %d\n",i,a[i]);
}