泛型归并排序

#define SENTINEL_CARD (-1)

#include <vector>

#include <algorithm>

#include <iterator>

#include <functional>

#include <iterator>

template<

class bidirectional_iterator,

template <class> class less_equal_compare = std::less_equal

>

class merge_sort_functor

{

public:

void operator()(

bidirectional_iterator p,

bidirectional_iterator r)const

{

size_t diff = distance(p,r);

if(diff <=1)

return;

if(diff >0)

{

bidirectional_iterator q = p;

advance(q, diff/2);

this->operator ()(p, q);

this->operator ()(q, r);

merge(p, q, r);

}

}

private:

void merge( bidirectional_iterator first,

bidirectional_iterator middle,

bidirectional_iterator last)const

{

using namespace std;

typedef less_equal_compare<bidirectional_iterator::value_type> le;

le le_comparer;

size_t n1 = distance(first, middle);

size_t n2 = distance(middle, last);

std::vector<int> L(first,middle);

std::vector<int> R(middle,last);

L.push_back(SENTINEL_CARD);

R.push_back(SENTINEL_CARD);

std::vector<int>::iterator i=L.begin(), j=R.begin();

for(bidirectional_iterator k=first; distance(k,last)>=0; ++k)

{

if(*i == SENTINEL_CARD)

{

std::copy(j, --R.end(), k);

return;

}

if(*j == SENTINEL_CARD)

{

std::copy(i, --L.end(), k);

return;

}

if( le_comparer(*i,*j) )

*k = *i++;

else

*k = *j++;

}

}

};

测试程序

int b[]={345,67,56,6,4567467,65768,7686,34635,67,57678,235};

vector<int> vi(b,b+sizeof(b)/sizeof(int));

list<int> li(b,b+sizeof(b)/sizeof(int));

merge_sort(b, 0, sizeof(b)/sizeof(int));

merge_sort_functor<vector<int>::iterator, std::less_equal>()

(vi.begin(), vi.end());

merge_sort_functor<list<int>::iterator, std::greater>()

(li.begin(), li.end());