1. // NOT WEAPONS GRADE. Lacks many usability features.
  2. // It's only a proof of concept for swap-only sorting in C++
  3.  
  4. #pragma once
  5.  
  6. #ifndef __HEAPSORT_H__
  7. #define __HEAPSORT_H__
  8.  
  9. namespace HeapSort
  10. {
  11.         namespace detail
  12.         {
  13.                 size_t left(size_t i)
  14.                 {
  15.                   return (2*i)+1;
  16.                 }
  17.                 size_t right(size_t i)
  18.                 {
  19.                   return (2*i)+2;
  20.                 }
  21.  
  22.                 template<typename T, typename Comparator>
  23.                 void sink(T *begin, size_t n, size_t idx, Comparator const &c)
  24.                 {
  25.                         for(size_t leftIdx=left(idx); leftIdx<n; leftIdx=left(idx))
  26.                         {
  27.                                 size_t rightIdx = right(idx);
  28.                                 T &leftItem = *(begin+leftIdx);
  29.                                 T &item = *(begin+idx);
  30.                                 if(rightIdx>=n)
  31.                                 {
  32.                                         using namespace std; // It will be used only as last resort for resolving swap()
  33.                                         if(c(item,leftItem))
  34.                                                 swap(item,leftItem);
  35.                                         return;
  36.                                 }
  37.                                 T &rightItem = *(begin+rightIdx);
  38.                                 if(c(rightItem,item) && c(leftItem,item))
  39.                                         return;
  40.                                 if(c(leftItem,rightItem))
  41.                                 {
  42.                                         using namespace std; // It will be used only as last resort for resolving swap()
  43.                                         swap(item,rightItem);
  44.                                         idx = rightIdx;
  45.                                         continue;
  46.                                 }
  47.                                 {
  48.                                         using namespace std; // It will be used only as last resort for resolving swap()
  49.                                         swap(item,leftItem);
  50.                                 }
  51.                                 idx = leftIdx;
  52.                         }
  53.                 }
  54.         } // namespace detail
  55.  
  56.         template<typename T,  typename Comparator>
  57.         void sort(T *begin, T *end, Comparator const &c = Comparator())
  58.         {
  59.                 size_t n = end-begin;
  60.                 if(n<=1)
  61.                         return;
  62.                 if(n==2)
  63.                 {
  64.                         if(c(*(begin+1),*begin))
  65.                         {
  66.                                 using namespace std; // It will be used only as last resort for resolving swap()
  67.                                 swap(*(begin+1),*begin);
  68.                         }
  69.                         return;
  70.                 }
  71.                 // #2
  72.                 for(int idx=n/2-1; idx>=0; --idx)
  73.                 {
  74.                         detail::sink(begin, n, idx, c);
  75.                 }
  76.                 // #3
  77.                 while(n>1)
  78.                 {
  79.                         {
  80.                                 using namespace std; // It will be used only as last resort for resolving swap()
  81.                                 swap(*begin,*(begin+n-1));
  82.                         }
  83.                         --n;
  84.                         detail::sink(begin, n, 0, c);
  85.                 }
  86.         }
  87.  
  88.         template<typename T>
  89.         void sort(T *begin, T *end)
  90.         {
  91.                 sort(begin,end,std::less<T>());
  92.         }
  93.  
  94. } // namespace HeapSort
  95.  
  96. #endif // __HEAPSORT_H__