/*
 Algoritmo de ordenação por intercalação (mergesort)

 Compare o tempo de execução desse programa com o tempo de execução de
 p17.c (algoritmo de ordenação por inserção (insertion sort)).

 $ mergesort 10 20 2020
 0 0 1 3 3 5 6 6 9 14 
 
 $ p17 10 20 2020
 0 0 1 3 3 5 6 6 9 14 
 
 $ time mergesort 100000 100000 2020 > /dev/null
 
 real	0m0.055s
 user	0m0.045s
 sys	0m0.005s
 $ time p17 100000 100000 2020 > /dev/null
 
 real	0m5.431s
 user	0m5.258s
 sys	0m0.030s 

 */

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

#define NMAX 1000000

void merge(int a[], int aux[], int lo, int mid, int hi);
void sortR(int a[], int aux[], int lo, int hi);
void sort(int a[], int N);

int main(int argc, char *argv[])
{
  int v[NMAX];
  int N = atoi(argv[1]), M = atoi(argv[2]), i;
  long seed = atol(argv[3]);

  if (N > NMAX) {
    printf("N muito grande\n");
    return 0;
  }

  srand(seed);
  for (i = 0; i < N; ++i)
    v[i] = M * (1.0 * rand()/(RAND_MAX + 1L));

  sort(v, N);

  for (i = 0; i < N; ++i)
    printf("%d ", v[i]);
  printf("\n");
  
  return 0;
}

/* stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
   precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays */
void merge(int a[], int aux[], int lo, int mid, int hi)
{
  int k; 
  int i = lo, j = mid + 1;

  /* copy to aux[] */
  for (k = lo; k <= hi; k++) 
    aux[k] = a[k];

  /* merge back to a[] */
  i = lo; j = mid + 1;
  for (k = lo; k <= hi; k++) {
    if      (i > mid)         a[k] = aux[j++];
    else if (j > hi)          a[k] = aux[i++];
    else if (aux[j] < aux[i]) a[k] = aux[j++];
    else                      a[k] = aux[i++];
  }
}

/* mergesort a[lo..hi] using auxiliary array aux[lo..hi] */
void sortR(int a[], int aux[], int lo, int hi) 
{
  int mid = lo + (hi - lo) / 2;
  if (hi <= lo) return;
  sortR(a, aux, lo, mid);
  sortR(a, aux, mid + 1, hi);
  merge(a, aux, lo, mid, hi);
}

/* mergesort a[0..N - 1] */
void sort(int a[], int N)
{
  int aux[NMAX];
  sortR(a, aux, 0, N - 1);
}