Merge Sort using vector c++

Question

I'm learning c++ and I know some algorithms and data structures. I was wondering what is the best way to do merge sort for a vector in c++.

// will write a program for merge sort
/* steps:
 * have an array of size n call it A
 * divide A into left and right halves L and R
 * call merge sort on the two halves now L' and R'
 * now merge the two halves into B (the sorted version of A)
 */
/* the merging algorithm:
 * the merging algorithm is a "two finger algo"
 * where an element of L' is compared with each elt of R' until the elt in R' is less
 * we then take this element and put it into our sorted array, B
 */
#include <iostream>
#include <vector> // will use the vector class  to make things like list slicing very easy

using namespace std;
void merge_sort(vector<int> &arr);
void merge(vector<int >&left, vector<int> &right, vector<int> &results);

int main() {
    vector<int> my_vector{10, 30, 50, 40};
    merge_sort(my_vector);

    for (int i: my_vector)
        cout << i << ',';
    return 0;
}

void merge_sort(vector<int> & arr) {
    if (arr.size() <= 1) return;

    int mid = arr.size() / 2;
    vector<int> left(arr.begin(), arr.end() - mid);
    vector<int> right(arr.begin() + mid, arr.end());

    merge_sort(left);
    merge_sort(right);
    merge(left, right, arr);
}
void merge(vector<int> &left, vector<int> &right, vector<int> &results)
{
    int L_size = left.size();
    int R_size = right.size();
    int i = 0, j = 0, k = 0;
    // two finger algorithm
    while (j < L_size && k < R_size) 
    {
        if (left[j] < right[k]) {
            results[i] = left[j];
            j++;
        }
        else {
            results[i] = right[k];
            k++;
        }
        i++;
    }
    while (j < L_size) {
        results[i] = left[j];
        j++; i++;
    }
    while (k < R_size) {
        results[i] = right[k];
        k++; i++;
    }
}
```

Answer 1

Overall

Looks good overall.

The design works perfectly for sorting integers. But in C++ we can potentially sort anything. So why not allow your sorting algorithm to work with any sortable type.

To do this learn templates:

 void merge_sort(vector<int> &arr);

 // Change to:

 template<typename T>
 void merge_sort(vector<T>& arr);

The next thing to think about is that vector<> is not the only thing that can be sorted. There are lots of container types that can be sorted. Normally we don't care about the container type and we abstract the container away and specific what what we want to sort in terms of iterators.

So the next subject to learn are iterarators'. Then you can specify what you want to sort in terms of the beginning and end of a range.

template<typename I>
void merge_sort(I begin, I end);

The next thing you should think about is the memory requirements your algorithm uses. Currently your algorithm uses 2 times the current size of the array you want to sort (in addition the vector). You can change this so you only use 1 times the current size of the vector.

To achieve this you want to allocate the memory once outside the recursive sort function then pass in this temporary memory into the merge sort.

// The wrapper
template<typename I>
void merge_sort(I begin, I end)

    // Create a single buffer are to be be re-used.
    std::vector<int>  tmpData(std::distance(begin, end));

    merge_sort_with_buffer(begin, end, std::begin(tmpData) std::end(tmpData));
}

template<typename I1, template I2>
void merge_sort_with_buffer(I1 b , I1 e, I2 tb, I2 te)
{
    std::size_t s = std::distance(begin, end);

    if (s < 2) {
        return;
    }

    I1 m   = std::next(begin, s/2);
    I2 tm  = std::next(tBegin, s/2);

    merge_sort_with_buffer(b, m, tb, tm);
    merge_sort_with_buffer(m, e, tm, te);
    merge(tb, tm, te, b);
}

template<typename I2, template I1>
void merge(I2 tb, I2 tm, I2 te, I1 dst)
{
    // copy tb->tm
    // copy tm->te
    //
    // To the destination
}

Code Review

Not a fan of bad comments:

#include <vector> // will use the vector class  to make things like list slicing very easy

Do you use slicing?

---

Stop doing this:

using namespace std;

It might be useful in books where space is limited. But in real code it actually causes problems. I recomend you stop using it because it becomes a habit. This is a bad one. When you have a bad habit you will just use it without thinking and accidentally cause on f the problems.

See: Why is “using namespace std;” considered bad practice? Personally I find the second answer the best.

---

In C++ it is more normal to put the & with the type in the declaration.

void merge_sort(vector<int> &arr);

// Like this:

void merge_sort(vector<int>& arr);

Note: This is the opposite of what is common in C.

---

Please always add the curly craces '{}'

    for (int i: my_vector)
        cout << i << ',';

    // Like this:

    for (int i: my_vector) {
        cout << i << ',';
    }

The trouble is people still make silly macros that are multiple lines. Not using the braces can put you in funny situations where only part of your code is executed by the loop when you least expect it.

More importantly to me it makes it much simpler to read.

---

In C++ the last return in main() is not needed.

    return 0;

If you don't provide one the compiler automatically adds a return 0 at the end of main.

It has been common practice to not include a return 0 if main does not ever return anything else. So if I see a return 0 at the end I start looking for other error detection code that would return another value.

---

This is a subtle one:

        if (left[j] < right[k]) {

If you use the less here then if they are equal you will choose the one from the right. Keep that in mind.

There is an important mathematical principle around sorting called "Stability" (when sorting). If items that are equal retain there original relative order the sort is considered stable otherwise it is not.

If you choose from the right when the items are equal your algorithm is not stable. So by using <= you automatically make your algorithm stable.

        if (left[j] <= right[k]) {

---

Note this is a copy operation:

        results[i] = left[j];

Now for integers this makes absolutely no different. But when you make this work for other types this mean copying an object. This can be expensive so we would prefer to use move rather than copy.

        results[i] = std::move(left[j]);

---

Sure these work.

    while (j < L_size) {
        results[i] = left[j];
        j++; i++;
    }
    while (k < R_size) {
        results[i] = right[k];
        k++; i++;
    }

But much easier to use standard algorithms

    std::copy(&left[j],  &left[L_size],  &result[i]);
    std::copy(&right[k], &right[R_size], &result[i]);

But then we remember that we want to use move rather than copy.

    std::move(&left[j],  &left[L_size],  &result[i]);
    std::move(&right[k], &right[R_size], &result[i]);