constexpr initialization of array to sort contents

Solution 1:

It's ugly, and probably not the best way to sort in a constant expression (because of the required instantiation depth).. but voilà, a merge sort:

Helper type, returnable array type with constexpr element access:

#include <cstddef>
#include <iterator>
#include <type_traits>

template<class T, std::size_t N>
struct c_array
{
    T arr[N];

    constexpr T const& operator[](std::size_t p) const
    { return arr[p]; }

    constexpr T const* begin() const
    { return arr+0; }
    constexpr T const* end() const
    { return arr+N; }
};

template<class T>
struct c_array<T, 0> {};

append function for that array type:

template<std::size_t... Is>
struct seq {};

template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...> {};

template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...> {};

template<class T, std::size_t N, class U, std::size_t... Is>
constexpr c_array<T, N+1> append_impl(c_array<T, N> const& p, U const& e,
                                      seq<Is...>)
{
    return {{p[Is]..., e}};
}
template<class T, std::size_t N, class U>
constexpr c_array<T, N+1> append(c_array<T, N> const& p, U const& e)
{
    return append_impl(p, e, gen_seq<N>{});
}

Merge sort:

template<std::size_t Res, class T, class It, std::size_t Accum,
         class = typename std::enable_if<Res!=Accum, void>::type >
constexpr c_array<T, Res> c_merge(It beg0, It end0, It beg1, It end1,
                                  c_array<T, Accum> const& accum)
{
    return
beg0 == end0  ? c_merge<Res>(beg0  , end0, beg1+1, end1, append(accum, *beg1)) :
beg1 == end1  ? c_merge<Res>(beg0+1, end0, beg1  , end1, append(accum, *beg0)) :
*beg0 < *beg1 ? c_merge<Res>(beg0+1, end0, beg1  , end1, append(accum, *beg0))
              : c_merge<Res>(beg0  , end0, beg1+1, end1, append(accum, *beg1));
}
template<std::size_t Res, class T, class It, class... Dummies>
constexpr c_array<T, Res> c_merge(It beg0, It end0, It beg1, It end1,
                                  c_array<T, Res> const& accum, Dummies...)
{
    return accum;
}

template<class T, std::size_t L, std::size_t R>
constexpr c_array<T, L+R> c_merge(c_array<T, L> const& l,
                                  c_array<T, R> const& r)
{
    return c_merge<L+R>(l.begin(), l.end(), r.begin(), r.end(),
                        c_array<T, 0>{});
}


template<class T>
using rem_ref = typename std::remove_reference<T>::type;

template<std::size_t dist>
struct helper
{
    template < class It >
    static constexpr auto merge_sort(It beg, It end)
    -> c_array<rem_ref<decltype(*beg)>, dist>
    {
        return c_merge(helper<dist/2>::merge_sort(beg, beg+dist/2),
                       helper<dist-dist/2>::merge_sort(beg+dist/2, end));
    }
};
template<>
struct helper<0>
{
    template < class It >
    static constexpr auto merge_sort(It beg, It end)
    -> c_array<rem_ref<decltype(*beg)>, 0>
    {
        return {};
    }
};
template<>
struct helper<1>
{   
    template < class It >
    static constexpr auto merge_sort(It beg, It end)
    -> c_array<rem_ref<decltype(*beg)>, 1>
    {
        return {*beg};
    }
};

template < std::size_t dist, class It >
constexpr auto merge_sort(It beg, It end)
-> c_array<rem_ref<decltype(*beg)>, dist>
{
    return helper<dist>::merge_sort(beg, end);
}

Helpers for usage example:

template<class T, std::size_t N>
constexpr std::size_t array_size(T (&arr)[N])  {  return N;  }

template<class T, std::size_t N>
constexpr T* c_begin(T (&arr)[N])  {  return arr;  }

template<class T, std::size_t N>
constexpr T* c_end(T (&arr)[N])  {  return arr+N;  }

Usage example:

constexpr int unsorted[] = {5,7,3,4,1,8,2,9,0,6,10}; // odd number of elements
constexpr auto sorted = merge_sort<array_size(unsorted)>(c_begin(unsorted),
                                                         c_end(unsorted));

#include <iostream>
int main()
{
    std::cout << "unsorted: ";
    for(auto const& e : unsorted) std::cout << e << ", ";
    std::cout << '\n';

    std::cout << "sorted: ";
    for(auto const& e : sorted) std::cout << e << ", ";
    std::cout << '\n';
}

Output:

unsorted: 5, 7, 3, 4, 1, 8, 2, 9, 0, 6, 10, 
sorted: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

Solution 2:

I know that this is an old question but as we have C++14 (and C++17 soon), and since C++14 constexpr rules aren't so restricted, and, for sure, couple of people will find your question in google, here is how quicksort (and of course other algorithms) can be done since C++14. (big credits to @dyp for constexpr array)

#include <utility>
#include <cstdlib>

template<class T>
constexpr void swap(T& l, T& r)
{
    T tmp = std::move(l);
    l = std::move(r);
    r = std::move(tmp);
}

template <typename T, size_t N>
struct array
{
    constexpr T& operator[](size_t i)
    {
        return arr[i];
    }

    constexpr const T& operator[](size_t i) const
    {
        return arr[i];
    }

    constexpr const T* begin() const
    {
        return arr;
    }
    constexpr const T* end() const
    {
        return arr + N;
    }

    T arr[N];
};

template <typename T, size_t N>
constexpr void sort_impl(array<T, N> &array, size_t left, size_t right)
{
    if (left < right)
    {
        size_t m = left;

        for (size_t i = left + 1; i<right; i++)
            if (array[i]<array[left])
                swap(array[++m], array[i]);

        swap(array[left], array[m]);

        sort_impl(array, left, m);
        sort_impl(array, m + 1, right);
    }
}

template <typename T, size_t N>
constexpr array<T, N> sort(array<T, N> array)
{
    auto sorted = array;
    sort_impl(sorted, 0, N);
    return sorted;
}

constexpr array<int, 11> unsorted{5,7,3,4,1,8,2,9,0,6,10}; // odd number of elements
constexpr auto sorted = sort(unsorted);

#include <iostream>
int main()
{
    std::cout << "unsorted: ";
    for(auto const& e : unsorted) 
      std::cout << e << ", ";
    std::cout << '\n';

    std::cout << "sorted: ";
    for(auto const& e : sorted) 
      std::cout << e << ", ";
    std::cout << '\n';
}

LIVE DEMO