1
\$\begingroup\$

I'm still learning C++ and also algorithms. So I'm expecting to do a lot of refactoring. Here's my code

#include <iostream>
#include <vector>
#include <iterator>

std::vector<int> mergesort(std::vector<int> &);
std::vector<int> merge(std::vector<int> &, std::vector<int> &);
std::vector<int>::iterator get_midpoint(std::vector<int> &);

int main()
{
  std::vector<int> vect;
  int num = 0;
  while(std::cin >> num)
  {
    vect.push_back(num);
  }
  std::vector<int> temp_vect = mergesort(vect);
  for(int num: temp_vect) {
    std::cout << num  << std::endl;
  }

}

std::vector<int> mergesort(std::vector<int> &unsorted_vector)
{
  std::vector<int>::iterator middle = unsorted_vector.begin();
  std::vector<int> sorted_vect, first_half, second_half, first_temp, second_temp;
  if(unsorted_vector.size() == 1) {
    return unsorted_vector;
  } else {
    middle = get_midpoint(unsorted_vector);
    first_temp.insert(first_temp.begin(), unsorted_vector.begin(), middle);
    second_temp.insert(second_temp.begin(), middle, unsorted_vector.end());
    first_half = mergesort(first_temp);
    second_half = mergesort(second_temp);
    sorted_vect = merge(first_half, second_half);
    return sorted_vect;
  }
}

std::vector<int> merge(std::vector<int> & first_vect, std::vector<int> & second_vect)
{
  std::vector<int> sorted_vect;
  auto first_it = first_vect.begin(),
        second_it = second_vect.begin();

  while(first_it != first_vect.end() && second_it != second_vect.end()) {
      if(*first_it < *second_it) {
        sorted_vect.push_back(*first_it);
        first_it++;
      } else {
        sorted_vect.push_back(*second_it);
        second_it++;
      }
  }

  sorted_vect.insert(sorted_vect.end(), first_it, first_vect.end());
  sorted_vect.insert(sorted_vect.end(), second_it, second_vect.end());

  return sorted_vect;
}

std::vector<int>::iterator get_midpoint(std::vector<int> &vect)
{
  std::vector<int>::iterator it = vect.begin();
  int middle = 0;
  if(vect.size() % 2 == 0) {
    middle =  vect.size() / 2;
  } else {
    middle = (vect.size() - 1) / 2;
  }
  std::advance(it, middle);
  return it;
}
\$\endgroup\$
1
\$\begingroup\$
  1. I think you input routine is not really safe. maybe add an explicit break?

    while (true) {
        cin >> num;
        if (cin.fail)
            break;
        vect.push_back(num);
    }
    
  2. What happens when unsorted_vector is empty. You check for size == 1 maybe turn that into size <= 1

  3. Stuff like this is hard to read:

    std::vector<int> sorted_vect, first_half, second_half, first_temp, second_temp;
    

    I would definitely suggest to put every name onto its own line and add the explicit type. Its not that you are saving trees here.

  4. Do not use else after an early exit.

    if(unsorted_vector.size() == 1) {
        return unsorted_vector;
    } else {
    // Stuff
    }
    

    Is equivalent to:

    if(unsorted_vector.size() == 1) {
        return unsorted_vector;
    }
    // Stuff
    

    However with less indentation and easier control flow.

  5. You should definitely reserve memory in your merge function:

    vector<int> sorted_vect;
    sorted_vect.reserve(first_vect.size()+second_vect.size());
    
  6. Use descriptive names. This is purely subjective, but whenever I see vect and friends i cringe. What do you really save from ommitting "or"?

\$\endgroup\$
  • 2
    \$\begingroup\$ You point (1) is wrong. The OP does it the correct way. Your code works but is over complex. \$\endgroup\$ – Martin York Sep 12 '16 at 16:23
  • \$\begingroup\$ May I ask why do I need to reserve memory in number 5? \$\endgroup\$ – Rafael Adel Sep 12 '16 at 23:46
  • \$\begingroup\$ Speed, if you do not allocate the known memory requirements beforehand, it might come to frequent reallocations of the vector as it grows. It goes as follows: The system allocates the memory necessary for your vector (0). When you push back it tries to allocate adjacent memory every push back. Now it might happen, that there is not enough continuous memory, so the whole vector gets reallocated somewhere else. Worst case this happens every push back. Conversely if you use reserve beforehand the system will reallocate at maximum once. \$\endgroup\$ – miscco Sep 13 '16 at 6:33
0
\$\begingroup\$

The get_midpoint can be simplified a lot:

std::vector<int>::iterator get_midpoint(std::vector<int> &vect)
{
    return vect.begin() + vect.size()/2;
}

You don't need to check size() for even/odd value, the integer division will work in your favour in this case, so 3/2 = 1.

And random_access/bidirectional/forward iterators have overloaded + operator, so you can add the result directly to begin(). The std::advance would be helpful when you would use container which has only InputIterator available (can increment, but only by single step). Then it can be still somewhat simplified to:

std::vector<int>::iterator get_midpoint(std::vector<int> &vect)
{
    auto it = vect.begin();
    std::advance(it, vect.size()/2);
    return it;
}

(I would also write /2 as >>1, but I think the compiler will optimize that one anyway, just old habits from ASM times die hard).


One more note about the rest of code:

I don't like how you use plenty of additional temporary vectors. When you want to enjoy C++ performance boost, you have to be a bit more aware of data structure, as that's the major advantage of C++ over other high-level languages.

Usually the sorting algorithms are implemented to either work above the initial container memory without any temporary, or when temporary is required, only single secondary vector of full size is created.

Then internal calls pass the first/last iterators to point to the parts of the vector memory, which should be processed in the particular inner call. If you need temporary vector, one of full size should provide enough temporary space for the operation, being properly partitioned by first/last iterators.

I'm sorry to not provide the example, but I believe you can find some merge sort implementations on the Internet, probably showing operation on 1-2 vector's only without the insert copying of content between internal calls.


edit:

When designing the algorithm, design also "memory". Where the data are stored, how much of them, why (purpose), when you want to create (temporary) copy, or when you want to use std::move semantics, etc. I'm not suggesting to go after full "Data-Oriented Design" (unless you are designing some big-data processing application, where performance is main goal), but still some level of awareness how your data are flowing under the hood is good to have.

Often by keeping data life cycle lean and without useless moving around, you will not only gain performance, but also simpler algorithm implementation and less code written = less bugs.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.