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 malloc
s 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 free
ing 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.