// NOT WEAPONS GRADE. Lacks many usability features.
// It's only a proof of concept for swap-only sorting in C++
#pragma once
#ifndef __HEAPSORT_H__
#define __HEAPSORT_H__
namespace HeapSort
{
namespace detail
{
size_t left(size_t i)
{
return (2*i)+1;
}
size_t right(size_t i)
{
return (2*i)+2;
}
template<typename T, typename Comparator>
void sink(T *begin, size_t n, size_t idx, Comparator const &c)
{
for(size_t leftIdx=left(idx); leftIdx<n; leftIdx=left(idx))
{
size_t rightIdx = right(idx);
T &leftItem = *(begin+leftIdx);
T &item = *(begin+idx);
if(rightIdx>=n)
{
using namespace std; // It will be used only as last resort for resolving swap()
if(c(item,leftItem))
swap(item,leftItem);
return;
}
T &rightItem = *(begin+rightIdx);
if(c(rightItem,item) && c(leftItem,item))
return;
if(c(leftItem,rightItem))
{
using namespace std; // It will be used only as last resort for resolving swap()
swap(item,rightItem);
idx = rightIdx;
continue;
}
{
using namespace std; // It will be used only as last resort for resolving swap()
swap(item,leftItem);
}
idx = leftIdx;
}
}
} // namespace detail
template<typename T, typename Comparator>
void sort(T *begin, T *end, Comparator const &c = Comparator())
{
size_t n = end-begin;
if(n<=1)
return;
if(n==2)
{
if(c(*(begin+1),*begin))
{
using namespace std; // It will be used only as last resort for resolving swap()
swap(*(begin+1),*begin);
}
return;
}
// #2
for(int idx=n/2-1; idx>=0; --idx)
{
detail::sink(begin, n, idx, c);
}
// #3
while(n>1)
{
{
using namespace std; // It will be used only as last resort for resolving swap()
swap(*begin,*(begin+n-1));
}
--n;
detail::sink(begin, n, 0, c);
}
}
template<typename T>
void sort(T *begin, T *end)
{
sort(begin,end,std::less<T>());
}
} // namespace HeapSort
#endif // __HEAPSORT_H__