/****************************************************************************
fision.cc

what is fusion sorting : sorting of an array very fast. The two fatest means to
sort an array are fusion sorting and quicksort. Here is a version of the first one.

fusion sorting of an array (the array is defined in the main) and the result 
is given by the function triFusion. See main, it's two lines.

specificity : fusion sorting is usually slow because one has to reserv a new
array for each recursive call. It is not the case here and this version of
fusion sorting should have the same efficiency as quicksort (thought much more simplier).

arno@salk.edu, Arnaud Delorme, CNL / Salk Institute, 2001

This program is free software; you can redistribute it and/or
modify it.  
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

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

#include <stdio.h>

double *tabtmp;

double *fusion(double *tab1, double *tab2, int size1, int size2)
{
  int i=0;
  int j=0;
  while ((i<size1) + (j<size2))
    {
      if (j==size2) { tabtmp[i+j] = *(tab1+i); i++; }
      else 
	if (i==size1) { tabtmp[i+j] = *(tab2+j); j++; }
	else 
	  if (*(tab1+i) > *(tab2+j)) { tabtmp[i+j] = *(tab2+j); j++; }
	  else { tabtmp[i+j] = *(tab1+i); i++; }
    }

  for (i=0; i<(size1+size2); i++)
    tab1[i] = tabtmp[i];

  return tab1;
}

double *sortFusion(double *tab, int size)
{
  if (size>2)
    {
      int size1 = size >> 1;
      int size2 = size - size1;
      double *tab1 = sortFusion(tab, size1);
      double *tab2 = sortFusion(tab + size1, size2);
      
      return fusion(tab1, tab2, size1, size2);
    }
  else
    {
      if (size > 1) if (*tab > *(tab+1)) { double tmp = *tab; *tab = *(tab+1); *(tab+1) = tmp; }
      return tab;
    }
}

double *triFusion(double *tab, int size)
{
  tabtmp = new double[size];
  return sortFusion(tab, size);
}


void main()
{
  double tab[] = { 8 , 9 , 16 , 3 ,17 , 8, 9, 5, 4, 18, 36, 44 };
  int size = 12;

  double *res = triFusion(tab, size);

  for (int i = 0; i < size; i++)
    printf("%3.2f\t", res[i]);
  printf("\n");

}