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

/*********************************************************************
 */
void merge(TYPE X[], int m, int n, TYPE B[])
{
  int k = 0, i = 0, j = m;
  
  while (k < m && j < (m + n)) {
    add_comparisons(1);
    add_assignments(1);
    if (X[ k ] <= X[ j ])
      B[ i++ ] = X[ k++ ];
    else
      B[ i++ ] = X[ j++ ];
  }
  
  if (j >= (m + n)) {
    while (k < m) {
      add_assignments(1);
      B[ i++ ] = X[ k++ ];
    }
  }
  else {
    while (j < (m + n)) {
      add_assignments(1);
      B[ i++ ] = X[ j++ ];
    }
  }
  
}


/*
 * Non-recursive merge sort
 */
void mergesort(TYPE A[], int left, int rigth)
{
  int i, cursor, left1, rigth1, left2, rigth2, 
    nelements = rigth - left + 1,
    size = 1,
    runs = nelements / size + ((nelements % size) ? 1 : 0),
    in_original = 1;
  TYPE *B, *T;
  
  
  B = (TYPE *)malloc(nelements*sizeof(TYPE));
  if (B == NULL) {
    printf("Out of memory?\n");
    exit(1);
  }
  while (size < nelements) {
    cursor = left;
    for (i = 1; i <= (runs / 2); ++i) {
      left1 = cursor;
      left2 = left1 + size;
      rigth1 = left2 - 1;
      rigth2 = (((rigth1 + size) > rigth) ? rigth : rigth1 + size);
      merge(&A[ cursor ], rigth1 - left1 + 1, rigth2 - left2 + 1, &B[ cursor ]);
      cursor += (rigth2 - left1 + 1);
    }
    if ((runs % 2) == 1) {
      add_assignments((rigth - cursor + 1)); 
      for (i = cursor; i <= rigth; ++i)
	B[ i ] = A[ i ];
    }
    
    /* let's switch the merging areas */
    in_original = (in_original + 1) % 2;
    T = A;
    A = B;
    B = T;
    size = size << 1;
    runs = nelements / size + ((nelements % size) ? 1: 0);
  }
  if (in_original == 0) { /* if items are in B */
    add_assignments(nelements); 
    for (i = left; i <= rigth; ++i)
      B[ i ] = A[ i ];
  }
  A = B;
}