#ifndef QUICKSORT_H
#define QUICKSORT_H


// Quicksort partitioning code.
// Chooses first element as pivot; reorders container and returns
// an iterator i so that:
//    - *i = pivot;
//    - all elements between first and i are <= pivot;
//    - all elements between i+1 and last are >= pivot.

template <class Iterator, class T>
Iterator partition(Iterator first, Iterator last, T*) 
{
  T pivot = *first;
  Iterator left = first;
  Iterator right = last;
  while (1)
  {
    do ++left; while (left != last && *left < pivot);
    do --right; while (right != first && *right > pivot);
    if (right < left)
      break;
    else
      std::iter_swap(left, right);
  }
  
  std::iter_swap(first, right);  // put pivot into correct position
  return right;
}


// Quicksort stub.

template <class Iterator, class T>
void quicksort(Iterator first, Iterator last, T*) 
{
  // FILL IN IMPLEMENTATION HERE.
}


// 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