CODEWITHSUNDEEP
c++vectoriteratormergesort
Ayush
Ayush

Reputation: 42450

MergeSort a vector using Iterators

For a class assignment, I am required to mergeSort a vector using its iterators.

I wrote the following that works on vectors, but does not use iterators:

void MergeSort(IntVector &vec, int left, int right)
{
     if (left < right)
     { 
          int nMid = ((left + right) / 2);
          MergeSort(vec, left, nMid);
          MergeSort(vec, nMid + 1, right);

          //merge(vec, left, nMid, right);
     }
}

I tried making some changes to accomodate iterators, but it doesn't allow me to perform operations such as < and + on iterators.

void MergeSort(IntVectorIt left, IntVectorIt right)
{
     if (left < right)
     { 
          intVectorIt nMid = ((left + right) / 2);
          MergeSort(left, mid);
          MergeSort(mid + 1, right);

          //merge(vec, left, nMid, right);
     }
}

How can I accomodate the use of Iterators in my mergesort?

FYI, these are the typedefs I use:

typedef vector<int> IntVector;
typedef IntVector::iterator IntVectorIt;

Upvotes: 0

Views: 2423

Answers (2)

Blindy
Blindy

Reputation: 67487

You want to compare if the iterators are the same (only error condition possible with sane input):

 if (left!=right)

As for your addition concerns, you're thinking of it wrong. Semantically adding left and right makes no sense since it goes past the end of your array, not to mention it will overflow. What you want is to add half the distance between them to left:

IntVectorIt nMid=left+(right-left)/2;

Upvotes: 3

MAK
MAK

Reputation: 26586

Instead of left<right, you have to use *left<*right.

Upvotes: 1

Related Questions