C++ Mergesort Implementation

I am currently in the process of learning C++. As such, I am making small programs to get more comfortable with the language. One of these programs is a small mergesort function with a basic wrapper for human-readable output and a few utility functions. I have posted this program here to get feedback on it.

I am most interested in feedback on these things (although don't hesitate to include anything else):

• The while loop near the end of the mergesort function in mergesort.cpp

• Naming conventions, primarily in the realm of capitalization. I tried to follow the standard library in this regard, but, I have seen other programs that follow a more Java-like convention. Which is preferred and why? If the Java-like conventions are preferred, why does the C++ library not follow them?

• Performance: specifically, are there any things I am doing blatantly wrong, but, also are there any small things I can do to improve (ie. to be more CPU cache aware or reduce register-swaps)?

Some notes:

• I know that using a function pointer to compare the objects to be sorted along with templates to allow for multiple object types to be sorted would be good, but, I have not yet learned templates in C++ and I see the function pointers as (correct me if I'm wrong) as only marginally useful for such a function without the ability to use any object type as the sortee.

The entirety of the source code is available on GitHub for easy viewing, cloning, etc.: https://github.com/john01dav/CPlusPlusMergeSortExample

It is also available here in accordance with the rules of this StackExchange:

mergesort.cpp:

```
#include

#include "vectorutils.h"
#include "mergesort.h"

using std::vector;

void mergesort(vector &vec){
//find midpoints in array
vector::size_type midpoint = vec.size() / 2;
vector::iterator midpoint_iter = vec.begin() + midpoint;

//split main array into two subarrays
vector vector_a, vector_b;

for(auto i=vec.begin();i!=midpoint_iter;++i){
vect

Lets answer you questions first:


The while loop near the end of the mergesort function in mergesort.cpp

while(vec_a_pos != vector_a.end() || vec_b_pos != vector_b.end()){ //I am especially interested in ways to improve this loop
    if(vec_a_pos == vector_a.end()){
        vec.push_back(*(vec_b_pos++));
    }else if(vec_b_pos == vector_b.end()){
        vec.push_back(*(vec_a_pos++));
    }else{
        vec.push_back(*vec_a_pos < *vec_b_pos ? *(vec_a_pos++) : *(vec_b_pos++));
    }
}

It looks like it works. But when I see the merge sort I usually see the empty array cases have been yanked out of the loop.

// Now your main loop only has one conditional branch.
while(vec_a_pos != vector_a.end() && vec_b_pos != vector_b.end())
{
    vec.push_back(*vec_a_pos < *vec_b_pos
                      ? *(vec_a_pos++)
                      : *(vec_b_pos++));
}
// One of these two is going to be a no-op.
// But it does not matter. Both work at top speed with no tests.
std::move(vec_a_pos, std::end(vector_a), std::back_inserter(vec));
std::move(vec_b_pos, std::end(vector_b), std::back_inserter(vec));

Naming conventions, primarily in the realm of capitalization. I tried to follow the standard library in this regard, but, I have seen other programs that follow a more Java-like convention. Which is preferred and why? If the Java-like conventions are preferred, why does the C++ library not follow them?

• There is no specific global naming convention.

-
But a common one is (this is the one that I use and is suggested by Bjorne S).

• User defined types (class/struct/enum) have an initial capital letter

• Objects (variables/functions) have an initial lower case letter.

You have to note that the "MOST" important part of C++ is the types. and knowing which identifier is a type and which is an object is very important so this naming convention helps you see when a type is being used.

blaBla(1, 2, 3);  // lower case letter => function call.
                  //                      or functor call on object.

BlaBla(1, 2, 3);  // upper case letter => Type being constructed.
                  //                      result is a temporary object

Whether you use '_' or upper case letters to separate words is very developer dependant. Just be careful not to use '_' as the first character in an identifier (The rules about its use there are complex and even if you know the rules not everybody does).

Why does the standard not follow this convention. The standard got written over a long period (it was not all there in one shot) and as a result has a mixture of conventions. By the time the committee realized it need a convention it was too late now. But in the standard everything is lower case.


Performance: specifically, are there any things I am doing blatantly wrong, but, also are there any small things I can do to improve (ie. to be more CPU cache aware or reduce register-swaps)?

To be blunt that is the compilers job. If you are worrying about the low level architecture you are using the wrong language. You should be worrying about the algorithm efficiency not the register usage efficiency.

The most common thing done wrong by java devlopers is allocating code dynamically when a normal local object would do.

In your algorithm I would worry about space usage. You are using way too much for the current algorithm.

For integers you don't have to worry about the cost of moving objects as a copy and a move have the same cost. But in the general case you should prefer to move rather than copy when you can (a move can be a lot cheaper than a copy). Also your code may be generalized in the future and if you have already done the work then your function can be templatized with no extra work than adding template to the front of your function.


I know that using a function pointer to compare the objects to be sorted along with templates to allow for multiple object types to be sorted would be good, but, I have not yet learned templates in C++ and I see the function pointers as (correct me if I'm wrong) as only marginally useful for such a function without the ability to use any object type as the sortee.

First. We prefer "functors" to "functions". A functor is an object that behaves like a function.

A function pointer is hard for the compiler to optimize across (as you can not guarantee at compile time what is happening at runtime). But functors are built around types. The compiler is very good at optimizing around types and is likely to inline your comparitor if you use a functor. So yes even with int it can add efficiency to compare using a functor rather than a function.

Also it makes your code more flexible even for integers. Current you sort from low to high. But just adding a function you can sort from high to low without changing the code itself.

```
template>
void mergesort(vector &vec)
{
F compare;

// your code as normal all the way down.
// just change the code to

StackExchange Code Review Q#137909, answer score: 4