#ifndef QUICKSORT_H
#define QUICKSORT_H

#include "insertion_sort.h"


static const int insertion_sort_cutoff = 16;


// Quicksort partitioning code.
// Chooses "median-of-3" 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*) 
{
  Iterator mid = first + (last - first) / 2;
  Iterator final = last - 1;
  Iterator second = first + 1;

  // Arrange things so that:
  //   - largest of 3 is in final position
  //   - smallest of 3 is in second position
  //   - median of 3 is in first position
  std::iter_swap(mid, second);
  if (*second > *final)
    std::iter_swap(second, final);
  if (*first > *final)
    std::iter_swap(first, final);
  if (*second > *first)
    std::iter_swap(second, first);

  // We can now start the scan one position further in on each side.
  T pivot = *first;
  Iterator left = first + 1;
  Iterator right = last - 1;
  while (1)
  {
    // We can remove the extra checks due to sentinels.
    do ++left; while (*left < pivot);
    do --right; while (*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*) 
{
  if (last - first > insertion_sort_cutoff)
  {
    Iterator cut = partition(first, last, std::_Val_type(first));
    quicksort(first, cut);
    quicksort(cut + 1, last);
  }
  insertion_sort(first, last);
}


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