Toy algorithm.

heap_sort.hh

/*! \brief simple heap sorting algorithm in array
 *  \author Shylock Hg
 *  \date 2018-12-08
 *  \email tcath2s@gmail.com
 * */

#include <type_traits>
#include <algorithm>
#include <array>

#ifndef _HEAP_SORT_HH_
#define _HEAP_SORT_HH_

/*! \brief heapfy to max heap
    \param a the array
    \param root the heap root
    \param len the heap length
*/
template <typename ITEM, std::size_t COUNT>
void heapify(std::array<ITEM, COUNT>& a, int root, int len) {
        int left = 2*root + 1;  // left of root
        int right = 2*root + 2;  // right of root

        int top = root;
        if (left < len && a[top] < a[left]) {   // compare with left child
                top = left;
        }
        if (right < len && a[top] < a[right]) {   // compare with right child
                top = right;
        }

        if (top != root) {
                std::swap(a[root], a[top]);
                heapify(a, top, len);
        }
}

template <typename ITEM, std::size_t COUNT>
void heap_sort(std::array<ITEM, COUNT>& a) {
        if (0 == a.size())
                return;

        // building heap O(N)
        // heapify from last non-leaf node
        for (int i = a.size()/2-1; i >= 0; i--) {
                heapify(a, i, a.size());
        }

        // sorting array O(NlogN)
        for (int i = a.size()-1; i >= 0; i--) {
                // select maximum to tail
                std::swap(a[0], a[i]);
                // rebuild heap
                heapify(a, 0, i);
        }
}

#endif  //!< header guard

merge_sort.hh

/*! \brief 
 *  \author Shylock Hg
 *  \date 2018-12-08
 *  \email tcath2s@gmail.com
 * */

#include <type_traits>
#include <algorithm>
#include <array>
#include <vector>

#ifndef _MERGE_SORT_HH_
#define _MERGE_SORT_HH_

template <typename ITEM, std::size_t COUNT>
void merge(std::array<ITEM, COUNT>& a, int lo, int mid, int hi) {
        std::array<ITEM, COUNT> temp;

        int i = lo;
        int j = mid;
        int k = lo;
        while (i < mid || j < hi) {
                if (i == mid) {
                        temp[k] = a[j];
                        j++;
                } else if (j == hi) {
                        temp[k] = a[i];
                        i++;
                } else if (a[i] < a[j]) {
                        temp[k] = a[i];
                        i++;
                } else {
                        temp[k] = a[j];
                        j++;
                }
                k++;
        }

        for (k = lo; k < hi; k++) {
                a[k] = temp[k];
        }
}

template <typename ITEM, std::size_t COUNT>
void _merge_sort(std::array<ITEM, COUNT>& a, int lo, int hi) {
        if (lo < hi-1) {
                int mid = lo + (hi - lo)/2;
                _merge_sort(a, lo, mid);
                _merge_sort(a, mid, hi);
                merge(a, lo, mid, hi);
        }
}

template <typename ITEM, std::size_t COUNT>
void merge_sort(std::array<ITEM, COUNT>& a) {
        if (0 == a.size()) {
                return;
        }

        _merge_sort(a, 0, a.size());
}

#endif  //!< _MERGE_SORT_HH_

quick_sort.hh

/*! \brief 
 *  \author Shylock Hg
 *  \date 2018-12-08
 *  \email tcath2s@gmail.com
 * */

#include <type_traits>
#include <algorithm>
#include <array>

#ifndef _QUICK_SORT_HH_
#define _QUICK_SORT_HH_

template <typename ITEM, std::size_t COUNT>
int pivot(std::array<ITEM, COUNT>& a, int lo, int hi) {
        const int pivot = hi;
        int i = lo;
        for (int j = lo; j < pivot; j++) {
                if (a[j] < a[pivot]) {
                        std::swap(a[i], a[j]);
                        i++;
                }
        }
        std::swap(a[i], a[pivot]);
        return i;
}

template <typename ITEM, std::size_t COUNT>
void _quick_sort(std::array<ITEM, COUNT>& a, int lo, int hi) {
        if (lo < hi) {
                int p = pivot(a, lo, hi);
                _quick_sort(a, lo, p-1);
                _quick_sort(a, p+1, hi);
        }
}

template <typename ITEM, std::size_t COUNT>
void quick_sort(std::array<ITEM, COUNT>& a) {
        if (a.size() == 0) {
                return ;
        }
        _quick_sort(a, 0, a.size()-1);
}

#endif  //!< _QUICK_SORT_HH_