// *********************************************************************
//			Sorting Functions
// Some implementation of Sorting Algorithms.
// Initial version:	13/07/98
// *********************************************************************
//   $Id: Sort.H,v 1.1 1999/09/10 09:23:28 avillani Exp $


// Classical QuickSort implementation
template<class TheType>
void QuickSort(TheType *v, int l, int r)
{
  if (r > l) {			// There is at least one element
    int i = l - 1;
    int j = r;
    TheType pivot = v[r];	// The Pivot is the rightmost element
    TheType tmp;

    do {
      do
	i++;
      while (v[i] < pivot);	// Scan the vector toward the rights

      do
	j--;
      while ((v[j] > pivot) && (j>0));	//  Scan the vector toward the left

      tmp = v[i];		// Swap i with j
      v[i] = v[j];
      v[j] = tmp;

      // At the end we have all the elements less then pivot on the left and
      // the other on the right.
    } while (j > i);		// Repeat until we reach the center

    v[j] = v[i];		// Save in i the value of j
    v[i] = v[r];		// Save the pivot in i
    v[r] = tmp;			// Save in r (ex pivot) the value of i

    QuickSort(v, l, i-1);	// Sort the left side
    QuickSort(v, i+1, r);	// Sort the right side
  }
}


// Classical MergeSort implementation
template<class TheType>
void MergeSort(TheType *v, int l, int r)
{
  if (r > l) {
    int m = (r + l) / 2;
    MergeSort(v, l, m);
    MergeSort(v, m + 1, r);

    TheType *b = new TheType[r + 1];	// Support vector
    int i, j, k;

    for (i = m + 1; i > l; i--)
      b[i - 1] = v[i - 1];
    for (j = m; j < r; j++)
      b[r + m - j] = v[j + 1];
    for (k = l; k <= r; k++)
      v[k] = (b[i] < b[j]) ? b[i++] : b[j--];

    delete[] b;
  }
}


//  Bertossi's like MergeSort Implementation
template<class TheType>
void BMergeSort(TheType d[], int s)
{
    int c = s / 2;	// The splitting point

    if (s > 1) {
	BMergeSort(d, c);		// The first Half
	BMergeSort(d + c, s - c);	// The Socond half
	Merge(d, c, s);			// Merge the sequence
  }
}

// Merge together the two sorted sequence
template<class TheType>
void Merge(TheType v[], int mezzo, int lung)
{
  int i;

  TheType *b = new TheType[lung];	// Support vector

  register int k = i = 0;
  int j = mezzo;

  // Scan the two half
  while ((i < mezzo) && (j < lung)) {
    if (v[i] < v[j])	
      b[k] = v[i++];    
    else		
      b[k] = v[j++];
    k++;
  }

  // Maybe we have to copy some data from the first half to the end of the
  // sequence
  if (i < mezzo)
    for (j = 0; j < mezzo - i; j++)
      v[k + j] = v[i + j];

  // Copy back the values in the right position
  for (j = 0; j < k; j++)
    v[j] = b[j];
  
  delete b;
}