I was trying to practice C++ iterators by defining the very common mergesort algorithm when I encountered inconsistent program behavior. My question is NOT how to implement mergesort (which I both know and also realize has many example answers), but rather when creating recursive vectors using iterators that I receive inconsistent final results.
I'm aware that I could solve the issue by copying the values into L and R arrays through a for loop, but I would like to understand why using iterators is not working. This is running on CLION with C++ 14. This post Best way to extract a subvector from a vector? did not answer my question, as I'm creating vector similar to methods prescribed.
void merge2(vector<int> &arr, int l, int m, int r)
{
vector<int> L{arr.begin()+l, arr.begin()+m+1};
vector<int> R{arr.begin()+m+1,arr.begin()+r+1};
int i = 0, j = 0, k = l;
int n1 = m - l + 1;
int n2 = r - m;
while (i < (n1) && j < (n2)){
if (L[i]<=R[i]){ //R[i] is replaced by R[j]
arr[k] = L[i++];
}
else {
arr[k] = R[j++];
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while(j < n2){
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void merge2Sort(vector<int> &arr, int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
// int m = (l+r-l)/2;
// int m = l+(r-l)/2;
int m = (l+r)/2;
// Sort first and second halves
merge2Sort(arr, l, m);
merge2Sort(arr, m+1, r);
merge2(arr, l, m, r);
}
}
int main(int argc, char **argv){
vector<int> arr = {12, 11, 13, 5, 6, 7};
merge2Sort(arr, 0, arr.size()-1);
for(auto i = arr.begin(); i != arr.end(); i++){
cout << *i << " ";
}
return 0;
}
Sometimes I receive the correct answer 5 6 7 11 12 13 and other times the incorrect answer 5 6 7 11 13 12. The answer should not vary by attempt.
Correct Answer to reflect answer and comments. Answer corrects indexing error and relies upon iterators. Also noting from comments that vectors when initialized from iterators should use () and not {}.
template <class It>
void merge(It left, It middle, It right)
{
// Beeing generic, you need to retrieve the type.
using value_type = typename std::iterator_traits<It>::value_type;
// You can copy only the first half
std::vector<value_type> left_side_copy(left, middle);
It L = left_side_copy.begin();
It R = middle;
while (L != left_side_copy.end() && R != right)
{
if ( *L <= *R )
{
*left = *L;
++L;
}
else {
*left = *R;
++R;
}
++left;
}
// Copy only the leftovers, if there are any
std::copy(L, left_side_copy.end(), left);
}
template <class It>
void merge_sort(It left, It right)
{
if (auto dist = std::distance(left, right); dist > 1)
{
It middle = left + dist / 2;
merge_sort(left, middle);
merge_sort(middle, right);
merge(left, middle, right);
}
}
int main(void)
{
std::vector<int> arr {
5, 12, 11, 13, 5, 4, 7, 13, 6
};
merge_sort(arr.begin(), arr.end());
for(auto const &i : arr) {
std::cout << ' ' << i;
}
std::cout << '\n';
}
