-epvector * expairseq::bubblesort(epvector::iterator itbegin, epvector::iterator itend)
-{
- unsigned n=itend-itbegin;
-
- epvector * sp=new epvector;
- sp->reserve(n);
-
- epvector::iterator last=itend-1;
- for (epvector::iterator it1=itbegin; it1!=last; ++it1) {
- for (epvector::iterator it2=it1+1; it2!=itend; ++it2) {
- if ((*it2).rest.compare((*it1).rest)<0) {
- iter_swap(it1,it2);
- }
- }
- sp->push_back(*it1);
- }
- sp->push_back(*last);
- return sp;
-}
-
-epvector * expairseq::mergesort(epvector::iterator itbegin, epvector::iterator itend)
-{
- unsigned n=itend-itbegin;
- /*
- if (n==1) {
- epvector * sp=new epvector;
- sp->push_back(*itbegin);
- return sp;
- }
- */
- if (n<16) return bubblesort(itbegin, itend);
- unsigned m=n/2;
-
- epvector * s1p=mergesort(itbegin, itbegin+m);
- epvector * s2p=mergesort(itbegin+m, itend);
-
- epvector * sp=new epvector;
- sp->reserve(s1p->size()+s2p->size());
-
- epvector::iterator first1=s1p->begin();
- epvector::iterator last1=s1p->end();
-
- epvector::iterator first2=s2p->begin();
- epvector::iterator last2=s2p->end();
-
- while (first1 != last1 && first2 != last2) {
- if ((*first1).rest.compare((*first2).rest)<0) {
- sp->push_back(*first1);
- ++first1;
- } else {
- sp->push_back(*first2);
- ++first2;
- }
- }
-
- if (first1 != last1) {
- while (first1 != last1) {
- sp->push_back(*first1);
- ++first1;
- }
- } else {
- while (first2 != last2) {
- sp->push_back(*first2);
- ++first2;
- }
- }
-
- delete s1p;
- delete s2p;
-
- return sp;
-}
-