template <typename LST, typename X> struct FilterLT_X {
  typedef typename LST::Head H;
  typedef typename LST::Tail T;
  typedef typename FilterLT_X<T, X>::Result filtered_tail;

  typedef typename Neg<typename GT<H,X>::Result>::Result preserve_head;
  typedef typename IsNIL<filtered_tail>::Result nil_filtered_tail;

  typedef typename If<preserve_head, 
                      List<H, filtered_tail>, 
                      typename If<nil_filtered_tail, 
                                  NIL, 
                                  filtered_tail>::Result>::Result Result;
};

template <typename X> struct FilterLT_X<NIL, X> {
  typedef NIL Result;
};

template <typename LST, typename X> struct FilterGT_X {
  typedef typename LST::Head H;
  typedef typename LST::Tail T;
  typedef typename FilterGT_X<T, X>::Result filtered_tail;

  typedef typename GT<H,X>::Result preserve_head;
  typedef typename IsNIL<filtered_tail>::Result nil_filtered_tail;

  typedef typename If<preserve_head, 
                      List<H, filtered_tail>, 
                      typename If<nil_filtered_tail, 
                                  NIL, 
                                  filtered_tail>::Result>::Result Result;
};

template <typename X> struct FilterGT_X<NIL, X> {
  typedef NIL Result;
};

template <typename LST_1, typename LST_2> struct Concat {
  typedef typename LST_1::Head H;
  typedef typename LST_1::Tail temp;
  typedef typename Concat<temp, LST_2>::Result T;
  typedef List<H, T> Result;
};

template <typename LST_2> struct Concat<NIL, LST_2> {
  typedef LST_2 Result;
};

template <typename LST_1> struct Concat<LST_1, NIL> {  
  typedef LST_1 Result;
};

template <> struct Concat<NIL, NIL> {  
  typedef NIL Result;
};

template <typename LST> struct QuickSort {
  typedef typename LST::Head p;
  typedef typename LST::Tail T;
  typedef typename FilterLT_X<T, p>::Result lessers;
  typedef typename FilterGT_X<T, p>::Result greaters;

  typedef typename QuickSort<lessers>::Result sorted_lesser;
  typedef typename QuickSort<greaters>::Result sorted_greater;

  typedef typename Concat<sorted_lesser, typename Concat<List<p, NIL>, sorted_greater>::Result >::Result Result;
};

template<> struct QuickSort<NIL> {
  typedef NIL Result;
};