#ifndef QUICKSORT_H
#define QUICKSORT_H


static const int insertion_sort_cutoff = 16;


// Quicksort stub.

template <class Iterator, class T>
void quicksort(Iterator first, Iterator last, T*) 
{
  std::pair<Iterator, Iterator> stack[30];
  int top = 0;
  Iterator f = first;
  Iterator l = last;

loop:
  
  while (l - f > insertion_sort_cutoff)
  {
    // Partition inline.
    Iterator mid = f + (l - f) / 2;
    Iterator final = l - 1;
    Iterator second = f + 1;

    std::iter_swap(mid, second);
    if (*second > *final)
      std::iter_swap(second, final);
    if (*f > *final)
      std::iter_swap(f, final);
    if (*second > *f)
      std::iter_swap(second, f);

    T pivot = *f;
    while (1)
    {
      do ++second; while (*second < pivot);
      do --final; while (*final > pivot);
      if (final < second)
	break;
      else
	std::iter_swap(second, final);
    }
  
    std::iter_swap(f, final);  // put pivot into correct position

    int left_size = final - f;
    int right_size = l - final - 1;
    if (left_size < right_size)
    {
      if (right_size > insertion_sort_cutoff)
      {
	stack[top++] = std::make_pair(final + 1, l);
	l = final;
      }
      else // both halves below cutoff
	break;
    }
    else
    {
      if (left_size > insertion_sort_cutoff)
      {
	stack[top++] = std::make_pair(f, final);
	f = final + 1;
      }
      else // both halves below cutoff
	break;
    }
  }

  // Is the stack empty yet?
  if (top)
  {
    --top;
    f = stack[top].first;
    l = stack[top].second;
    goto loop;
  }

  // Insertion sort inline.
  if (first < last)
  {
    for (Iterator i = first + 1; i != last; ++i)
    {
      T x = *i;

      // Special case: if x is the smallest item, avoid all the
      // comparisons and move it directly to the front of the container.
      if (x < *first) 
      {
	Iterator dest = i;
	Iterator src = i;
	while (src != first)
	{
	  --src;
	  *dest = *src;
	  --dest;
	}
	*first = x;
      } 
      
      // Otherwise, if x is not the smallest, we are guaranteed to
      // have a "sentinel" that ensures the inner loop below will
      // terminate, and we do not have to check to keep from going
      // past the begining of the container.
      else
      {
	Iterator src = i;
	Iterator dest = i;
	--src;
	while (x < *src) 
	{
	  *dest = *src;
	  dest = src;
	  --src;
	}
	*dest = x;
      }
    }
  }
}


// Auxiliary function to instantiate template correctly.
// You can ignore this.

template <class Iterator> inline
void quicksort(Iterator first, Iterator last)
{
  quicksort(first, last, std::_Val_type(first));
}


#endif