#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;

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

  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*) 
{
  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