Merge sort implementation in C++

Question

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

// Add the leftovers
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);
}}

Answer 1

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.