# Merge sort implementation in C++

I was wondering if this implementation of merge sort could be improved. Are there any things that I have done wrong?

void merge(int *a, int *l, int leftCount, int *r, int rightCount) {
int i = 0, j = 0, k = 0;

// Compare l and r and add it to a
while (i < leftCount && j < rightCount) {
if (l[i] < r[j]) {
a[k++] = l[i++];
}
else {
a[k++] = r[j++];
}
}

while (i < leftCount) {
a[k++] = l[i++];
}
while (j < rightCount) {
a[k++] = r[j++];
}}

void mergeSort(int *a, int n) {
if (n >= 2) {
int mid, i, *l, *r;
mid = n / 2;

/* Create left and right subarrays */
// Mid elements from index 0 till mid - 1
l = (int*)malloc(mid * sizeof(int));
// From n - mid till n - 1
r = (int*)malloc((n - mid) * sizeof(int));

// Fill left subarray
for (i = 0; i < mid; i++) {
l[i] = a[i];
}
// Fill right subarray
for (i = mid; i < n; i++) {
r[i - mid] = a[i];
}

// Sort left subarray
mergeSort(l, mid);
// Sort right subarray
mergeSort(r, n - mid);

// Merge l and r in a
merge(a, l, mid, r, n-mid);

// Free the memory
free(l);
free(r);
}}

• This is C. Although C++ compiler can compile it, I don't think writing in a C way is optimal in general (although it might have some niche usages). Nov 11, 2017 at 12:18

# Algorithm

mergesort allocates a new buffer of scratch memory for each recursive call. This means sorting an array has to use $O(n \log n)$ allocations total, with $2 * n$ peak memory usage. This is double the amount of memory usually required, and if mallocs runtime complexity is worse than $O(1)$, the whole mergesort operation will perform worse than $O(n \log n)$.

Also, every call to mergesort unnecessarily copies all of the elements of the previous buffer into the new ones. These copies can be completely skipped with appropriate management of the already existing buffers.

The merge operation isn't stable, though it can trivially be made so by changing l[i] < r[i] to l[i] <= r[i]. Stability is usually a major factor for choosing merge sort!

# Implementation

• Unnecessary restriction on int - this algorithm could be used for any comparable type with templates.
• malloc/free or new/delete should usually be used sparingly. In your case, what would speak against the use of either a std::vector<int> or (preferably) gsl::span<int>, or at the very least a std::unique_ptr<int[]>? Both release their memory just fine in case of exceptions (which the current code doesn't even begin to check: results of malloc are never tested!), and freeing the memory will be done automatically once the objects leave the scope.
• Naming: Many variables have short, cryptic names that do not express their intentions clearly. What reads easier, l[i] = a[i]; or left_buffer[index] = original[index];?

# Fixes

Trying to keep faithful to the original, but including the improvements suggested:

template<typename Element>
void merge(Element *target, Element *source, size_t left_start, size_t right_start, size_t right_end) {
auto target_index = left_start, left_end = right_start;
auto left_index = left_start, right_index = right_start;

while(left_index < left_end && right_index < right_end) {
if(source[left_index] <= source[right_index]) {
target[target_index++] = source[left_index++];
} else {
target[target_index++] = source[right_index++];
}
}

while(left_index < left_end) {
target[target_index++] = source[left_index++];
}

while(right_index < right_end) {
target[target_index++] = source[right_index++];
}
}

template<typename Element>
void merge_sort(Element *original, Element *buffer, size_t start, size_t end) {
auto distance = end - start;
if(distance < 2) return;
auto mid = start + distance / 2;

merge_sort(buffer, original, start, mid);
merge_sort(buffer, original, mid, end);

merge(original, buffer, start, mid, end);
}

template<typename Element>
void merge_sort(Element *original, size_t size) {
auto buffer = std::make_unique<Element[]>(size);

for(auto index = 0u; index < size; ++index) {
buffer[index] = original[index];
}

merge_sort(original, buffer.get(), 0, size);
}


merge basically just gets a slightly different signature (as I'm passing around indices to indicate different buffers instead of pointers).
merge_sort got split into two functions: One to do the actual sorting, and one to setup the extra buffer. Note the reuse of the original array as buffer!
Also note that the elements get copied into the buffer beforehand. This is done so the cascading between buffers works in all cases ($\lceil\log_2 n\rceil$ might be odd = the lowest merge would start copying from the wrong buffer, or $n$ is not a power of 2 = recursion depth might differ by 1 for different parts of the array). This copy step could conceivably be moved elsewhere (or, under certain circumstances, be skipped entirely), but this way the implementation is much clearer about when the copy is done.

# Further improvements

• merge_sort could use a different sorting algorithm once the number of elements in a part goes below a threshold in order to improve overall performance.
• merge_sort could be extended to support iterators, instead of just plain arrays.
• Hello, I tried today to use your version of the merge sort algorithm but when I pass an array it does not sort it. When I print the array after using the merge_sort I get the same output as before sorting it. Am I missing something? The array that I pass looks like this: int arr[] = { 3,4,1,2,55,32,53 };. Nov 12, 2017 at 12:15
• @puls99: Sorry, had a parameter of merge wrong (should be mid instead of start + distance). Fixed. Nov 12, 2017 at 16:47