1 #ifndef __JTOOLS__JMERGESORT__
2 #define __JTOOLS__JMERGESORT__
49 template<
class JElement_t>
66 template<
class JSuperContainer_t,
template<
class,
class>
class JContainer_t,
class JAllocator_t>
68 JContainer_t<JElement_t, JAllocator_t>& output)
const
70 (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
81 template<
class JSuperContainer_t,
template<
class,
class>
class JContainer_t,
class JAllocator_t,
class JComparator_t>
83 JContainer_t<JElement_t, JAllocator_t>& output,
84 const JComparator_t& comparator)
const
86 (*this)(input.begin(), input.end(), output, comparator);
97 template<
class T,
template<
class,
class>
class JContainer_t,
class JAllocator_t>
100 JContainer_t<JElement_t, JAllocator_t>& output)
const
102 (*this)(__begin, __end, output, std::less<JElement_t>());
114 template<
class T,
template<
class,
class>
class JContainer_t,
class JAllocator_t,
class JComparator_t>
117 JContainer_t<JElement_t, JAllocator_t>& output,
118 const JComparator_t& comparator)
const
124 for (
unsigned int i =
std::distance(__begin, __end); i != 0; i >>= 1) {
136 this->
merge(__begin, __end, comparator);
150 template<
class JContainer_t>
151 static inline void copy(
const JContainer_t& input,
154 int n = input.size();
158 typename JContainer_t::const_iterator in = input .begin();
161 for ( ;
n != 0; --
n, ++in, ++out) {
179 template<
class JContainer_t,
class JComparator_t>
180 static inline void merge(
const JContainer_t& first,
181 const JContainer_t& second,
183 const JComparator_t& comparator)
185 int n = (first .size() - 1 +
188 output.resize(
n + 1);
190 typename JContainer_t::const_iterator i = first .begin();
191 typename JContainer_t::const_iterator
j = second.begin();
194 for ( ;
n != 0; --
n, ++out) {
196 if (comparator(*i,*
j)) {
223 }
else if (level - 1 <
buffer.size()) {
228 return buffer[level - 1].first;
231 return buffer[level - 1].second;
248 template<
class _Iterator_t,
class JComparator_t>
249 inline void merge(_Iterator_t __begin,
251 const JComparator_t& comparator,
252 const unsigned int level = 0,
274 this->
merge(__begin, __begin + N/2, comparator, level + 1,
LEFT);
275 this->
merge(__begin + N/2, __end, comparator, level + 1,
RIGHT);