bitonic_sort.hpp

#include <sprout/index_tuple.hpp>
#include <sprout/array.hpp>
#include<utility>
#include<type_traits>
namespace detail {
//ここからバイトニック成分
namespace impl
{
	template<class T, class>struct Bitonic_Marge_impl;

	template<class T, std::size_t ...Idxs>
	struct Bitonic_Marge_impl<T, std::index_sequence<Idxs...>>
	{
		static const std::size_t Size = sizeof...(Idxs);
		using array = sprout::array<T, Size>;

		template<std::size_t Len, std::size_t Idx>
		constexpr static T exchange(array const&v)
		{
			constexpr std::size_t other = Idx^Len;
			return(other < Size) && ((Idx < other) ^ (v[Idx] < v[other])) ? v[other] : v[Idx];
		}		
		
		template<class Len>
		constexpr static array apply(array const&v, Len)
		{
			constexpr std::size_t I = Len::value;
			return apply(array{{ exchange<I, Idxs>(v)... }}, std::integral_constant<std::size_t, I / 2>{});
		}
		constexpr static array apply(array const&v, std::integral_constant<std::size_t, 0>)
		{
			return v;
		}
	};
    template<std::size_t N0, std::size_t N1, class T, std::size_t...Idxs>
	constexpr static sprout::array<T, N0 + N1>
		bitonic_cat(sprout::array<T, N0>const&v0, sprout::array<T, N1>const&v1,
		std::index_sequence<Idxs...>)
	{
        return{ {((Idxs < N0) ? v0[N0 - Idxs - 1] : v1[Idxs - N0])... }};
	}
   
}
    
    

//ここまで

template <typename T, std::size_t N1, std::size_t N2>
constexpr sprout::array<T, N1 + N2> merge_sort_merge(
    const sprout::array<T, N1>& arr1, const sprout::array<T, N2>& arr2) {
    return impl::Bitonic_Marge_impl<T,std::make_index_sequence<N1+N2>>
        ::apply(
            impl::bitonic_cat(arr1,arr2,std::make_index_sequence<N1+N2>{})
            ,std::integral_constant<std::size_t, 2048>{}//マジックナンバー。あとで治したい
            );
}
//http://fimbul.hateblo.jp/entry/2014/06/04/025051
template <typename IndexTuple>
struct merge_sort_split;
template <sprout::index_t... Indices>
struct merge_sort_split<sprout::index_tuple<Indices...>> {
  template <typename T, sprout::index_t>
  struct indexed_type {
    typedef T type;
  };

  template <typename T, typename... Types>
  static constexpr sprout::array<T, sizeof...(Indices) + sizeof...(Types)> eval(
      const typename indexed_type<T, Indices>::type&... args1,
      const Types&... args2) {
    return merge_sort_merge(
        merge_sort_split<typename sprout::index_range<
            0, sizeof...(Indices) / 2>::type>::template eval<T>(args1...),
        merge_sort_split<typename sprout::index_range<
            0, sizeof...(Types) / 2>::type>::template eval<T>(args2...));
  }
};
template <>
struct merge_sort_split<sprout::index_tuple<>> {
  template <typename T>
  static constexpr sprout::array<T, 0> eval() {
    return sprout::array<T, 0>{{}};
  }
  template <typename T>
  static constexpr sprout::array<T, 1> eval(const T& arg) {
    return sprout::array<T, 1>{{arg}};
  }
};

template <typename T, typename... Types>
constexpr sprout::array<T, sizeof...(Types)> merge_sort_impl2(
    const Types&... args) {
  return merge_sort_split<typename sprout::index_range<
      0, (sizeof...(Types) / 2)>::type>::template eval<T>(args...);
}

template <typename T, std::size_t N, sprout::index_t... Indices>
constexpr sprout::array<T, N> merge_sort_impl1(
    sprout::index_tuple<Indices...>&&, const sprout::array<T, N>& arr) {
  return merge_sort_impl2<T>(arr[Indices]...);
}

}  // detail

template <typename T, std::size_t N>
constexpr sprout::array<T, N> merge_sort(const sprout::array<T, N>& arr) {
  return detail::merge_sort_impl1(sprout::index_range<0, N>::make(), arr);
}


//Test
template<std::size_t...Idxs>
constexpr auto make_test(std::index_sequence<Idxs...>)
{
    return sprout::array<int,sizeof...(Idxs)>{{(Idxs*79%128)...}};
}
int main() {
    constexpr auto arr=make_test(std::make_index_sequence<1160>{});
    
    constexpr auto result = merge_sort(arr);
  for (auto&& i : result) {
    std::cout << i << ' ' << std::flush;
  }
  std::cout << std::endl;
}