Merge Sort C++11 C++17

Question

Question

Any way I can optimize this further using new C++11 or C++17 features? Would also like feedback on my variable naming, memory management, and style (notice my placement of varible_name++ in some areas), and how I've abstracted the sort into a recursive_merge_sort function and a merge function.

Code

#include <iostream>

void merge(int* data, int low, int mid, int high)
{
    int low_copy = low;
    int mid_copy = mid;

    int size = high - low;
    int* sorted = new int[size];
    int i = 0;

    while(low_copy < mid && mid_copy < high) {
        if(data[low_copy] < data[mid_copy]) {
            sorted[i] = data[low_copy++];
        }
        else {
            sorted[i] = data[mid_copy++];
        }
        ++i;
    }

    while(low_copy < mid) {
        sorted[i++] = data[low_copy++];
    }
    while(mid_copy < high) {
        sorted[i++] = data[mid_copy++];
    }

    for(i = 0; i < size; ++i) {
        data[low + i] = sorted[i];
    }
}

void recursive_merge_sort(int* data, int low, int high) {
    if(low >= high - 1) { return; }

    int mid = (high + low) / 2;
    recursive_merge_sort(data, low, mid);
    recursive_merge_sort(data, mid, high);

    merge(data, low, mid, high);
}

void merge_sort(int* data, int num_elements) {
    recursive_merge_sort(data, 0, num_elements);
}

int main()
{
    int data[] = { 5, 1, 4, 3, 65, 6, 128, 9, 0 };
    int num_elements = 9;

    std::cout << "unsorted\n";
    for(int i=0; i < num_elements; ++i) {
        std::cout << data[i] << " ";
    }

    merge_sort(data, num_elements);

    std::cout << "\nsorted\n";
    for(int i=0; i < num_elements; ++i) {
        std::cout << data[i] << " ";
    }

    return 0;
}

Answer 1

Design

Passing data with high and low works. But is equivalent to data+low and data+high. And just passing two values.

This is what is referred to as an Iterator range. If you look at the standard library you will see that a lot of the concepts hinge around iterators you should look that up and understand how it works.

Code Review

For every call to new there should be a call to delete.

    int* sorted = new int[size];

Or so the old text books tell us. In modern C++ you probably should never call new or delete (unless you know its a good idea).

But here you are leaking memory because you don't release it. You should add a delete [] sorted; to the end of the function.

BUT leaving the new/delete in your code is not a good idea. It's not exception safe to start with. So simply declare a vector<int> here and let it manage the memory for you.

We should also note that memory management is very expensive. So rather than doing this every loop. Why not do it once at the beginning and reuse the memory.

Sure this works:

    while(low_copy < mid && mid_copy < high) {
        if(data[low_copy] < data[mid_copy]) {
            sorted[i] = data[low_copy++];
        }
        else {
            sorted[i] = data[mid_copy++];
        }
        ++i;
    }

But we could simplify it:

     for(;low_copy < mid && mid_copy < high; ++i) {
        sorted[i] = (data[low_copy] < data[mid_copy])
                       ? data[low_copy++];
                       : data[mid_copy++];
    }

Also when you see loops like this you should look at the standard algorithms to see if there is one that will do all that work for you.

Another thing to note is that you are copying the value from data to sorted. This is fine for integers, but you should be able to sort nearly any C++ type and copying a C++ type is not usually the most efficient way to get the value from one location to another. You should look up the concept of moving. When the type being sorted is a bit more complex moving it (rather than copying is usually a better idea).

These loops can definitely be done by standard algorthims:

    while(low_copy < mid) {
        sorted[i++] = data[low_copy++];
    }
    // Or 
    std::copy(data + low_copy, data + mid, sorted + i);
    // Or (when you move objects)
    std::move(data + low_copy, data + mid, sorted + i);

This is subject to overflow.

    int mid = (high + low) / 2;

Common mistake. If high and low are both large then this could easily overflow. Do the division fist (on the difference). Then add to the low.

    int mid = low + (high - low) / 2;

Are you sure there are 9 elements?

    int data[] = { 5, 1, 4, 3, 65, 6, 128, 9, 0 };
    int num_elements = 9;

Common source of errors. Don't manually do stuff the compiler can work out correctly. This is especially true if data is subsequently modified (and human person can make mistakes) does not change num_elements.

    int data[] = { 5, 1, 4, 3, 65, 6, 128, 9, 0 };
    int num_elements = sizeof(data)/sizeof(data[0]);

In more modern versions of C++ we even have a standard way of doing it:

    int num_elements = std::size(data);

No need for this in main:

    return 0;

Answer 2

1. If you have a range from start till end, why do you describe it with a base-pointer and two indices, instead of two pointers or a pointer and a size?
   Equivalently for the split range passed to merge().

2. You are allocating a new array on each call to merge().
   Why not just do a single allocation in the base merge_sort()?

3. Also, you are leaking it.

4. Using the ternary operator condition ? true_expr : false_expr would simplify some of your code.

5. return 0; is implicit for main().

That should be enough to get you started.