Merge sort using c++ vectors

Question

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;
}

Answer 1

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"?

Answer 2

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.