# Trying for an efficient and readable merge-sort implementation

My first implementation of merge sort in C++.

I'm looking for any sort of optimization and/or conventional practice tips, such as using the appropriate data types and naming my variables appropriately.

#include <iostream>

void print_array(int[], size_t);

void merge_sort(int[], size_t, size_t);

int main() {
size_t size;

std::cout << "Enter the size of the container: ";
std::cin >> size;

int arr[size];
for (size_t i = 0; i < size; ++i) {
std::cout << "[" << i+1 << "] Enter the next integer element: ";
std::cin >> arr[i];
}

std::cout << std::endl << "Unsorted array: ";
print_array(arr, size);
std::cout << std::endl << std::endl;

merge_sort(arr, 0, size-1);

std::cout << "Sorted array: ";
print_array(arr, size);
}

void print_array(int arr[], size_t size) {
for (size_t i = 0; i < size; ++i) {
std::cout << arr[i] << ' ';
}
}

void merge_sort(int arr[], size_t start, size_t end) {
if (end > start) {
size_t middle = (start+end)/2;

merge_sort(arr, start, middle);
merge_sort(arr, middle+1, end);

int l[middle-start+1];
int r[end-middle];

for (size_t i = start; i <= middle; ++i) {
l[i-start] = arr[i];
}

for (size_t i = middle+1; i <= end; ++i) {
r[i-(middle+1)] = arr[i];
}

size_t i = 0, j = 0, k = start;
while (i < middle-start+1 && j < end-middle) {
if (l[i] < r[j]) {
arr[k] = l[i++];
} else {
arr[k] = r[j++];
}
++k;
}

for (size_t z = i; z < middle-start+1; ++z) {
arr[k] = l[z];
++k;
}

for (size_t z = j; z < end-middle; ++z) {
arr[k] = r[z];
++k;
}
}
}

• I think you mean it's a merge function written in C, with a main that uses C++ just for cin and cout. – JDługosz May 17 at 22:11
• I'm new man, cut me some slack. – mastmartelli May 18 at 0:30

Let's start up top:

void print_array(int[], size_t);

void merge_sort(int[], size_t, size_t);


You declare two functions here, but what are their semantics? For a start, be aware that this is just a different spelling for

void print_array(int*, size_t);

void merge_sort(int*, size_t, size_t);


So, both functions receive a pointer as first argument. I for one avoid the syntax you used, exactly because it obfuscates the fact that you're passing pointers, not arrays. I've gotten into discussions over this topic though and others actually like this syntax to represent pointers to the first element of an array.

Now that we have these declarations, one question is what they are supposed to do with the memory the first parameter points to. Also, secondary, I'd wonder how they behave if you pass them a null pointer. Those are things worth documenting, but also the use of const is a valuable tool. In particular, it should be void print_array(int const*, size_t) instead.

Now, concerning the first function, I'd guess that it's an array (from the name) so the pointer is to the first element and the second parameter gives the size. You could prevent some guessing by naming the parameters in the declaration.

Concerning the second function, I can't guess what the parameters mean. Yes, there seems to be an array, but I have no idea what the second size_t parameter is supposed to mean. If you just want to sort the sequence, why not just pass a pointer to its first element and its size, just like the first function?

Now, let's look at the code in main(): The first thing, which other pointed out as well, is the use of variable length arrays. Replace that with std::vector<int>. This should be your fallback whenever you need a dynamic array and don't have any additional requirements that make it unsuitable. I'd suggest you fix that first, then adjust the input and also pass a reference to the vector to the two functions. That also avoids having to document how the functions behave with null pointers, because that's eliminated as an option. For the second function, you will have to split it, one part receiving the vector by reference, the other part that works recursively will still have to use pointers.

Let's move on to the actual sorting function. The first thing there is

if (end > start) {
...
}


You have a single condition that skips the whole function. Some people actually prefer having only a single exit point for a function, so they use this style. I personally prefer using the opposite condition and an early return. My rationale is that this way I can split the function in my mind. The part above is an initial condition which I can assume is met in the code below. Splitting it up means either part has a reduced complexity, making it easier (or even possible) to understand. In addition, you don't get deeply indented code.

As a side effect, it makes you look at the condition, end > start, which determines whether you have to sort something. Now, using end <= start isn't much better, but maybe it leads to end - start <= 0, so if you have zero elements left you can just leave. Then, it might strike you: You can as well leave if you only have one element left, because a sequence with zero or one element is always sorted!

Looking at the remaining code, there are three sections. The first is the two loops copying arr into two temporary arrays. The second does some work on those three arrays. The last part combines the two temporary arrays into arr again. One thing to improve there is to split these parts visually, maybe even add a sentence or two that explain how the code below works and why. Don't document what it does though, because that's what you see from reading the code! In many cases, you don't need any comments for the "how" part, but the "why" part is important, because it captures your decisions.

Finally, let's get to the most difficult part: Naming variables. Good names are start, middle and end. Not so well names are l and r for the two temporary arrays. Maybe spelling out left and right would help. Alternatively, head and tail, front and back. As a rule of thumb, the larger the scope of a variable is, the more speaking its name should be.

• The single most important advantage of merge sort is its stability. The elements compared equal retain their original order. Your code loses stability. If l[i] compares equal to r[j], the latter is merged first.

• Your code assumes closed ranges (that is, end is a valid index). That leads to some unpleasant fiddling with indices. Semi-open ranges (that is, end is the first invalid index) are much cleaner to deal with.

• size_t middle = (start+end)/2; is vulnerable to arithmetic overflow. Consider

  size_t middle = start + (end - start)/2;

• Avoid VLAs. They are vulnerable to stack overflow, and besides, they are not supported by standard.

• No naked loops, please. Every loop implements an algorithm, and therefore deserves a name. The before and after the actual merge in fact implement copy.

• I don't see anything resembling . The entire code is plain old .

• 1. std::midpoint() is better in general, but as start never exceeds end, yours works too. A surprisingly thorny problem. 2. It's not hard to calculate that the VLAs add 2 * (end - start + 1) ints over all the stack-frames. Being concrete might drive the point home. 3. Yes, aside from <iostream>, it's very c-like. Still, compiled as C++ with extensions? It's code in a C++ dialect assiduously avoiding leveraging the language. – Deduplicator May 16 at 19:35

void merge_sort(int[], size_t, size_t);
I assume you mean to sort in-place since there is no output given. You should be taking two iterators, not a int* and two indexes. Look at the signatures for the std::sort functions and its family!

for (size_t i = start; i <= middle; ++i) {
l[i-start] = arr[i];
}


All those loops looks copying part of the array... use the standard algorithm for that, not a loop.

You specifically mention readability. Calling named functions to copy a range of elements will be much more readable than making the reader reverse-engineer the loop to figure out what it means!

int l[middle-start+1];
int r[end-middle];


That's not even legal code. Apparently, gcc supports C's VLA as an extension.

It might be more efficient to just return a sorted vector rather than sorting in-place, since your implementation starts by copying the the entire array to a different location, anyway. Again, make your signature match the standard sort functions.

Don't use endl, as explained many many times here.

It would be a lot easier to test if you had test cases built-in rather than requiring input from the user each time. You could have several test arrays set up as constants and automatically check the results too!