// This program uses code from "Algorithms in C, Third Edition,"
//               by Robert Sedgewick, Addison-Wesley, 1998.


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

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 print_array(int * A, int length)
{
  int counter;
  for (counter = 0; counter < length; counter++)
  {
    printf ("%2d: %d\n", counter, A[counter]);
  }
  printf("\n");
}

void merge(Item *D, Item *B, int M, 
           Item *C, int P, Item * aux )
{ 
    int T = M+P;
    int i, j, k;
   
    for (i = 0; i < M; i++) aux[i] = B[i]; 
    for (j = 0; j < P; j++) aux[j+M] = C[j];
    
    for (i = 0, j = M, k = 0; k < T; k++)
    {
        if (i == M) { D[k] = aux[j++]; continue; }
        if (j == T) { D[k] = aux[i++]; continue; }
        if (less(aux[i], aux[j])) D[k] = aux[i++];
        else D[k] = aux[j++];
    }
} 

void msort_help2(Item * A, int L, int R, Item * aux)
{ 
   printf("start: msort(L = %d, R = %d)\n", L, R);
   print_array(A, 10);
   printf("-----------------------\n\n");
           
    if (R <= L) return;
    int M = (R+L)/2;
    msort_help2(A, L, M, aux);  
    msort_help2(A, M+1, R, aux);
 
    Item * B = &(A[L]);
    int N = M-L+1;
    Item * C = &(A[M+1]);
    int P = R-M;
    merge(B, B, N, C, P, aux);

   printf("end: msort(L = %d, R = %d)\n", L, R);
   print_array(A, 10);
   printf("-----------------------\n\n");
}

void mergesort2(Item * A, int length)
{
    Item * aux = malloc(sizeof(Item) * length);    
    
    msort_help2(A, 0, length-1, aux);
    free(aux);
}


void msort_help(Item * A, int length, Item * aux)
{ 
    if (length <= 1) return;
    int M = length/2;
    Item * C = &(A[M]);
    int P = length-M;

    msort_help(A, M, aux);  
    msort_help(C, P, aux);
 
    merge(A, A, M, C, P, aux);
}

void mergesort(Item * A, int length)
{
    Item * aux = malloc(sizeof(Item) * length);    
    
    msort_help(A, length, aux);
    free(aux);
}


int main()
{
   printf("start:\n\n");
//  int a[] = {17, 90, 70, 30, 60, 40, 45, 80, 10, 35}; 
  int a[] = {35, 30, 17, 10, 60, 90, 45, 80, 40, 70}; 
  print_array(a, 10);

  mergesort(a, 10); 

  print_array(a, 10);

  return 0;
}