3
\$\begingroup\$

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;
}
\$\endgroup\$
  • 4
    \$\begingroup\$ This is not much different from C, and there is a memory leak. Perhaps you could use a tool such as valgrind to detect memory leak and have a look at classic answer on implementation of sorting algorithms? \$\endgroup\$ – Incomputable Apr 28 at 17:56
  • 1
    \$\begingroup\$ This becomes much more interesting when you are sorting something not as trivial as int. Because C++ allows you to define the operator< for any type you can sort any type that can be compared. \$\endgroup\$ – Martin York Apr 29 at 6:25
  • \$\begingroup\$ Did you calculate how much memory your code allocates during sorting, say, a one thousand elements array? And how many times it invokes allocator function? \$\endgroup\$ – CiaPan Apr 29 at 11:44
  • \$\begingroup\$ I attempted to use valgrind, but ran into this issue on my OS stackoverflow.com/questions/52732036/… \$\endgroup\$ – greg Apr 30 at 4:29
7
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ For your std::copy example, why did you choose to add to the pointers instead of using var.begin() and var.end()? This must be an example of an Iterator range. \$\endgroup\$ – greg Apr 29 at 23:00
  • \$\begingroup\$ How did you determine what calculation you use for mid to over overflow here ` int mid = low + (high - low) / 2;`? \$\endgroup\$ – greg Apr 29 at 23:01
  • \$\begingroup\$ @greg: The std::copy() example is an example of replacing your where(){} loop. So it should use the same range. \$\endgroup\$ – Martin York Apr 29 at 23:39
  • 1
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Martin York Apr 29 at 23:42
  • 1
    \$\begingroup\$ @greg Note pointers are an implementation of the iterator concept. \$\endgroup\$ – Martin York Apr 30 at 6:32
3
\$\begingroup\$
  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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.