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

/*********************************************************************
 * We define logarithm of 2 by ourselves when compiling with Turbo C 
 */

#ifdef __TURBOC__
double log2(double x)
{
  double i = 1, j = 0;
  while (i < x) {
    i *= 2;
    j += 1;
  }
  return (j);
}
#endif


/*********************************************************************
 */

void insertion_sort(int A[], int low, int high)
{
  int i, j, temp;
  for (j = low + 1; j <= high; ++j) {
    add_assignments(1);
    temp = A[j];
    i = j - 1;
    while (i >= low && A[i] > temp) {
      add_comparisons(1);
      A[i + 1] = A[i];
      --i;
    }
    add_comparisons(1);
    add_assignments(1);
    A[i + 1] = temp;
  }
}


/*********************************************************************
 */

void swap2(int A[], int i, int j)
{
  int temp = A[i];
  add_assignments(3);
  A[i] = A[j];
  A[j] = temp;
}

/*********************************************************************
 */

void reverse2(int A[], int low, int high)
{
  int             t;
  for (t = 0; t < ((high - low + 1) >> 1); ++t)
    swap2(A, low + t, high - t);
}

/*********************************************************************
 */

void move_right(int A[], int low, int high, int k)
{
  if (k > 0) {
    reverse2(A, low, high);
    reverse2(A, high + 1, high + k);
    reverse2(A, low, high + k);
  }
}


/*********************************************************************
 */

void change_places(int A[], int buf, int xl, int xr)
{
  int temp;

  add_assignments(1);
  /* The hole is created */
  temp = A[buf];

  while (xl < xr) {
    add_assignments(2);
    A[buf++] = A[xl];
    A[xl++] = A[buf];
  }
  add_assignments(2);
  A[buf] = A[xl];
  A[xl] = temp;
}


/*********************************************************************
 * The procedure merges subarrays A[xl..xr] and A[yl..yr] into the
 * subarray A[buf..]. The elements in the result area are swapped with
 * the merged elements.  
 */
 
void straight_merge(int A[], int buf, int xl, int xr, int yl, int yr)
{
  int temp;
  add_assignments(1);
  /*
   * The hole is created by storing the first element (A[buf]) of
   * result area. By that we get rid of swap-operations.
   */
  temp = A[buf];
  while (xl < xr && yl < yr) {
    add_comparisons(1);
    add_assignments(2);
    if (A[xl] <= A[yl]) {
      A[buf++] = A[xl];
      A[xl++] = A[buf];
    } else {
      A[buf++] = A[yl];
      A[yl++] = A[buf];
    }
  }
  while (xl <= xr && yl <= yr) {
    add_comparisons(1);
    add_assignments(2);
    if (A[xl] <= A[yl]) {
      A[buf++] = A[xl];
      A[xl] = ((xl < xr) ? A[buf] : temp);
      ++xl;
    } else {
      A[buf++] = A[yl];
      A[yl] = ((yl < yr) ? A[buf] : temp);
      ++yl;
    }
  }
  if (buf == xl || buf == yl)
    return;
  add_assignments(1);
  /* The hole is created again */
  temp = A[buf];
  if (yl > yr) {
    while (xl < xr) {
      add_assignments(2);
      A[buf++] = A[xl];
      A[xl++] = A[buf];
    }
    add_assignments(2);
    A[buf] = A[xl];
    A[xl] = temp;
  } else {
    while (yl < yr) {
      add_assignments(2);
      A[buf++] = A[yl];
      A[yl++] = A[buf];
    }
    add_assignments(2);
    A[buf] = A[yl];
    A[yl] = temp;
  }
}


/*********************************************************************
 * The procedure search the highest index k, yl <= k <= yr, by
 * binarysearch for which the relation A[k] <= z is true. 
 */

int high_binary_search(int A[], int yl, int yr, int z)
{
  int mid, low = yl, high = yr;
  if (yr < yl)
    return (yl - 1);
  while ((high - low) >= 1) {
    mid = low + ((high - low + 1) >> 1);
    add_comparisons(1);
    if (A[mid] <= z)
      low = mid;
    else
      high = mid - 1;
  }
  add_comparisons(1);
  if (A[low] <= z)
    return (low);
  else
    return (low - 1);
}

/*********************************************************************
 * Ohjelma lomittaa lohkon A[xl..xr] lohkoon A[yl..yr]. Lohkot ovat
 * vierekkaisia, eli xr+1 == yl. Ensimmaisen lohkon alkioiden paikat
 * etsitaan kayttaen puolitushakua. Alkiot siirretaan paikalle
 * listakaannoilla.
 */
void pardo_forward_block_merge(int A[], int xl, int xr, int yl, int yr)
{
  int             h;
  while (xr - xl >= 0) {
    h = high_binary_search(A, xr + 1, yr, A[xl]);
    move_right(A, xl, xr, h - xr);
    xl = xl + h - xr + 1;
    xr = h;
  }
}

/*********************************************************************
 * The procedure merges subarrays A[xl..xr] and A[yl..yr] into the
 * subarray A[buf..] by binary merge. The elements in the result area
 * are swapped with the merged elements.  
 */

void binary_merge(int A[], int buf, int xl, int xr, int yl, int yr)
{
  int i, temp, m, n;
  m = xr - xl + 1;
  n = yr - yl + 1;
  add_assignments(1);
  /*
   * The hole is created by storing the first element (A[buf]) of
   * result area. By that we get rid of swap-operations.
   */
  temp = A[buf];
  while (m > 0 && n > 0) {
    if (m <= n) {
      i = yl + n / m - 1;
      add_comparisons(1);
      if (A[xl] >= A[i]) {
	while (yl < i) {
	  add_assignments(2);
	  A[buf++] = A[yl];
	  A[yl++] = A[buf];
	}
	add_assignments(2);
	A[buf++] = A[yl];
	A[yl] = ((yl < yr) ? A[buf] : temp);
	++yl;
	n = yr - yl + 1;
      } else {
	if ((yl - 1) != (i = high_binary_search(A, yl, i - 1, A[xl]))) {
	  while (yl < i) {
	    add_assignments(2);
	    A[buf++] = A[yl];
	    A[yl++] = A[buf];
	  }
	  add_assignments(2);
	  A[buf++] = A[yl];
	  A[yl] = ((yl < yr) ? A[buf] : temp);
	  ++yl;
	  n = yr - yl + 1;
	}
	add_assignments(2);
	A[buf++] = A[xl];
	A[xl] = ((xl < xr) ? A[buf] : temp);
	++xl;
	--m;
      }
    } else {
      i = xl + m / n - 1;
      add_comparisons(1);
      if (A[yl] >= A[i]) {
	while (xl < i) {
	  add_assignments(2);
	  A[buf++] = A[xl];
	  A[xl++] = A[buf];
	}
	add_assignments(2);
	A[buf++] = A[xl];
	A[xl] = ((xl < xr) ? A[buf] : temp);
	++xl;
	m = xr - xl + 1;
      } else {
	if ((xl - 1) != (i = high_binary_search(A, xl, i - 1, A[yl]))) {
	  while (xl < i) {
	    add_assignments(2);
	    A[buf++] = A[xl];
	    A[xl++] = A[buf];
	  }
	  add_assignments(2);
	  A[buf++] = A[xl];
	  A[xl] = ((xl < xr) ? A[buf] : temp);
	  ++xl;
	  m = xr - xl + 1;
	}
	add_assignments(2);
	A[buf++] = A[yl];
	A[yl] = ((yl < yr) ? A[buf] : temp);
	++yl;
	--n;
      }
    }
  }
  if (buf == xl || buf == yl)
    return;
  add_assignments(1);
  /* The hole is created again */
  temp = A[buf];
  if (n <= 0) {
    while (xl < xr) {
      add_assignments(2);
      A[buf++] = A[xl];
      A[xl++] = A[buf];
    }
    add_assignments(2);
    A[buf] = A[xl];
    A[xl] = temp;
  } else {
    while (yl < yr) {
      add_assignments(2);
      A[buf++] = A[yl];
      A[yl++] = A[buf];
    }
    add_assignments(2);
    A[buf] = A[yl];
    A[yl] = temp;
  }
}

/*********************************************************************
 * Non-recursive merge sort of the subarray A[left..rigth] by using
 * locations A[buf..left1-1] or A[rigth+1..buf] as the extra space. If
 * to_rigth is 0 then the buffer-area is in A[buf..left-1], else if
 * to_rigth is 1 then it is in A[buf..buf+rigth-left]. The assumption
 * is that |A[buffer-area]| = |A[left..rigth]|. 
 */

void two_way_msort(int A[], int left, int rigth, int buf, 
		   int to_rigth)
{
  int i, cursor, left1, rigth1, left2, rigth2, runs,
    size, nelements;
  nelements = rigth - left + 1;
  size = 1;
  while (size < nelements) {
    runs = nelements / size;
    if (nelements % size)
      ++runs;
    cursor = left;
    for (i = 1; i <= (runs >> 1); ++i) {
      left1 = cursor;
      left2 = left1 + size;
      rigth1 = left2 - 1;
      rigth2 = (((rigth1 + size) > rigth) ? rigth : rigth1 + size);
      straight_merge(A, buf, left1, rigth1, left2, rigth2);
      buf += (rigth2 - left1 + 1);
      cursor += (rigth2 - left1 + 1);
    }
    if (runs % 2 == 1) {	/* Number of runs was odd. */
      change_places(A, buf, cursor, rigth);
    }
    buf = left;
    if (to_rigth) {
      left += nelements;
      rigth += nelements;
      to_rigth = 0;
    } else {
      left -= nelements;
      rigth -= nelements;
      to_rigth = 1;
    }
    size = size << 1;
  }
}



/*********************************************************************
 * The procedure searches the smallest elements of two blocks
 * A[left..cut] and A[cut+1..rigth]. 
*/

void find_smallest_elements(int A[], int left, int cut, int rigth,
			    int *last1, int *last2)
{
  int bufsize, leftblocksize;
  bufsize = 0;
  leftblocksize = cut - left + 1;
  *last1 = left - 1;
  *last2 = cut;
  while (*last2 < rigth && bufsize < leftblocksize) {
    add_comparisons(1);
    if (A[*last1 + 1] <= A[*last2 + 1]) {
      *last1 = *last1 + 1;
      --leftblocksize;
    } else {
      *last2 = *last2 + 1;
    }
    ++bufsize;
  }
}


/*********************************************************************
 */

void simple_tkp(int A[], int left, int rigth)
{
  int start, end, buf, cut, nelements, half, nrounds_is_odd;
  cut = rigth;
  nelements = cut - left + 1;
  half = (nelements >> 1);
  if (nelements == 1)
    return;
  nrounds_is_odd = (int) ceil(log2((double) half)) % 2;
  if (nrounds_is_odd) {	/* Merging first to rigth. */
    buf = cut - half + 1;
    end = buf - 1;
    start = buf - half;
  } else {		/* Merging first to left. */
    end = cut;
    start = end - half + 1;
    buf = start - half;
  }
  two_way_msort(A, start, end, buf, nrounds_is_odd);
  cut = cut - half;
  nelements = cut - left + 1;
  half = (nelements >> 1);
  /* Handling of the	first n - O(sqrt(n)) elements */
  while (half >= (int) sqrt((double) rigth - left + 1)) {
    nrounds_is_odd = (int) ceil(log2((double) half)) % 2;
    if (nrounds_is_odd) {	/* Merging first to left. */
      buf = left;
      start = buf + half;
      end = start + half - 1;
      nrounds_is_odd = 0;
    } else {	/* Merging first to rigth. */
      start = left;
      end = start + half - 1;
      buf = end + 1;
      nrounds_is_odd = 1;
    }
    two_way_msort(A, start, end, buf, nrounds_is_odd);
    binary_merge(A, cut - half + 1, left, left + half - 1, cut + 1, rigth);
    cut = cut - half;
    nelements = cut - left + 1;
    half = (nelements >> 1);
  }
  /* Handling of the first O(sqrt(n)) elements */
  insertion_sort(A, left, left + nelements - 1);
  pardo_forward_block_merge(A, left, left + nelements - 1,
			    left + nelements, rigth);
}

/*********************************************************************
 * Sort the area A[left..rigth] with minimum space. First the second
 * half is sorted by using first half as the auxiliary space. Then the
 * first quarter is sorted by using the second quarter as the
 * auxiliary space, and merged with the sorted second half, into
 * locations starting from the second quarter. Now the first quarter
 * is handled similarly, leaving 1/8 of the array unsorted, and so on.
 * The process stops after log N phases, leaving the first element
 * unsorted. It is finally inserted to the correct position.  
 */

void tkp(int A[], int left, int rigth)
{
  int             start, end, buf, cut, nelements, half, nrounds_is_odd;
  cut = rigth;
  nelements = cut - left + 1;
  half = (nelements >> 1);
  if (nelements == 1)
    return;
  nrounds_is_odd = (int) ceil(log2((double) half)) % 2;
  if (nrounds_is_odd) {	/* Merging first to rigth. */
    buf = cut - half + 1;
    end = buf - 1;
    start = buf - half;
  } else {		/* Merging first to left. */
    end = cut;
    start = end - half + 1;
    buf = start - half;
  }
  two_way_msort(A, start, end, buf, nrounds_is_odd);
  cut = cut - half;
  nelements = cut - left + 1;
  half = (nelements >> 1);
  /* Handling of the	first n - O(n / log n) elements */
  while (nelements >= (rigth - left + 1) / log2((double) rigth - left + 1)) {
    nrounds_is_odd = (int) ceil(log2((double) half)) % 2;
    if (nrounds_is_odd) {	/* Merging first to left. */
      buf = left;
      start = buf + half;
      end = start + half - 1;
      nrounds_is_odd = 0;
    } else {	/* Merging first to rigth. */
      start = left;
      end = start + half - 1;
      buf = end + 1;
      nrounds_is_odd = 1;
    }
    two_way_msort(A, start, end, buf, nrounds_is_odd);
    binary_merge(A, cut - half + 1, left, left + half - 1, cut + 1, rigth);
    cut = cut - half;
    nelements = cut - left + 1;
    half = (nelements >> 1);
  }
  {
    int             last1, last2;
    /* Handling of the first O(n / log n) elements */
    simple_tkp(A, left, cut);
    /*
     * Searching of the smallest O(n / log n) elements of two
     * ordererd block, the first is left..cut and the other is
     * cut+1 ..rigth
     */
    find_smallest_elements(A, left, cut, rigth, &last1, &last2);
    /*
     * The smallest elements are in left..last1 and cut+1..last2
     * If the smallest elements are in front already, the job is
     * done.
     */
    if (last1 != cut)
      if (last2 == rigth)
	move_right(A, left, cut, rigth - cut);
      else {
	straight_merge(A, left, last1 + 1, cut, 1, 0);
	binary_merge(A, last2 - cut + last1 + 1, left,
		     left + cut - last1 - 1, last2 + 1, rigth);
	simple_tkp(A, left, last1 - left + 1 + last2 - cut);
      }
  }
}