C++: Merge Sort Implementation

Question

I have this code for Merge Sort. I want to improve this code. I have learned Here

that we should use Iterartor so that we can use any container. How to use iterator in this code.

#include <iostream>
#include <vector>
#include <algorithm>

template<class T>
void merge(std::vector<T>& v, int p, int q, int r)
{
int size1 = q-p+1;
int size2 = r-q;
std::vector<T> L(size1);
std::vector<T> R(size2);

for(int i = 0; i < size1; i++)
{
    L[i] = v[p+i];
}
for(int j = 0; j < size2; j++)
{
    R[j]=v[q+j+1];
}

int i=0,j=0;
int k;
for(k = p; k <= r && i < size1 && j < size2; k++)
{
    if(L[i] <= R[j])
    {
        v[k] = L[i];
        i++;
    }
    else
    {
        v[k] = R[j];
        j++;
    }
}
for(i = i; i < size1; ++i)
{
    v[k] = L[i];
    k++;
}

for(j = j; j < size2; j++)
    {
        v[k] = R[j];
        k++;
    }
}

template<class T>
void merge_sort(std::vector<T>& v, int p, int r){
if(p < r)
{
    int q = (p+r)/2;
    merge_sort(v, p, q);
    merge_sort(v, q+1, r);
    merge(v, p, q, r);
}
}

int main()
{
std::vector<int>vec;
vec.push_back(13);
vec.push_back(5);
vec.push_back(7);
vec.push_back(7);
vec.push_back(4);
vec.push_back(2);
vec.push_back(10);
int sz = vec.size();
std::cout << "Entered array : ";
for(int n = 0; n < sz; n++){
    std::cout << vec[n] <<" ";
}
std::cout << "\n";
std::cout << "Sorted array : ";
merge_sort(vec, 0, sz-1);
for(int n = 0; n < sz; n++){
    std::cout << vec[n] << " ";
}
std::cout << "\n";

std::vector<char> c;
c.push_back('d');
c.push_back('y');
c.push_back('h');
c.push_back('l');
c.push_back('e');
c.push_back('a');
int sz1 = c.size();
std::cout << "Entered array : ";
for(int n = 0; n < sz1; n++){
    std::cout << c[n] <<" ";
}
std::cout << "\n";
std::cout << "Sorted array : ";
merge_sort(c, 0, sz1-1);
for(int n = 0; n < sz1; n++){
    std::cout << c[n] << " ";
}
std::cout << "\n";

std::vector<std::string> str;
str.push_back("car");
str.push_back("dog");
str.push_back("apple");
str.push_back("ball");
str.push_back("tree");
int sz2 = str.size();

std::cout << "Entered array : ";
for(int n = 0; n < sz2; n++){
    std::cout << str[n] <<" ";
}
std::cout << "\n";
std::cout << "Sorted array : ";
merge_sort(str, 0, sz2-1);
for(int n = 0; n < sz2; n++){
    std::cout << str[n] << " ";
}
std::cout << "\n";

    return 0;
}

Answer 1

Some suggestions:

Why int for indices?

What if your input vector has 2^33 elements, and your system's sizeof(int) is 4? That's perfectly possible. Use std::vector<T>::difference_type (or perhaps std::vector<T>::size_type) for indices into the vector and std::vector<T>::size_type for its size.

(In some cases there's some benefit to using smaller indices, but I wouldn't worry about that in your situation.)

Why just std::vector?

While std::vector is a very useful data structure, it's not the only one we might use. In fact, we might just have a raw T* and a size_t length. You're forcing your client code to copy its data into a vector to have it sorted - which is quite unnecessary.

Now, the standard C++ library approach on this matter is to template on pairs of iterators - for the beginning and the end of the range you want to sort. Another acceptable alternative, but which will only work for a consecutive range of memory, is to use a gsl::span<T> (and you can easily extract a span from a vector using v.begin() and v.end()).

In the hopefully-near future you would be able to take a range, but this has not been standardized yet.

Use meaningful names

Suppose I want to use your merge_sort() function:

template<class T>
void merge_sort(std::vector<T>& v, int p, int r);

How would I know what is p and what is r? Even v I can only guess from its' type. At least use:

template<class T>
void merge_sort(std::vector<T>& data_to_sort, int start_index, int end_index);

... and see also the next point for an even better API.

Also, you have ps, qs and rs all over your code and it's confusing. So are L and R. Remember - the reader doesn't know what you meant, only what you wrote. And s/he shouldn't have to hold a lot of "semantic context" to read your code. Surely you'll agree this:

    auto start = start_index;
    auto end = end_index;
    if (start < end) {
        auto middle = (start + end ) / 2;
        merge_sort(data_to_sort, start,  middle);
        merge_sort(v, middle + 1, end);
        merge(data_to_sort, start, middle, end);
    }

is more readable than your main merge_sort() body.

Expose the API the client code would like to use

Let's ignore the iterators option for a second and stick with a vector. If I want to use your code, why should I type

merge_sort(my_vector, 0, my_vector.size() - 1);

...when I should be able to type just

merge_sort(my_vector);

...which has all the necessary information? Now in the implementation, you're using a range (via a pair of indices). But you should still offer me:

template<class T>
void merge_sort(std::vector<T>& data_to_sort) 
{
     return merge_sort(data_to_sort, 0, data_to_sort.size() - 1);
}

and consider putting the rest of your code within namespace detail.

If you switch to an iterator interface, this point might become moot.

Should you really be copying so much?

You're sorting Ts. Now, sizeof(T) could theoretically be quite large, in which case the swaps you perform during the merge are very costly. In those cases, it may be more reasonable to sort a permutation of array indices, which are "compared" by comparing their corresponding Ts. (If the comparison takes about the same time as copying the whole thing, perhaps it's not that much of an issue.)

I'm not saying you should rewrite your code now, just be aware of your implicit assumption

Your merge sort requires O(n) extra space, O(1) is possible

When merging, you allocate O(n) extra space - two vectors L and R. That's ok in many cases; but it's not the optimal thing to do, complexity-wise. It's actually possible to perform a merge sort with O(1) extra memory, still maintaining O(n log(n) time - as is established in this work by Katajainen , Pasanen and Teuhola.

Again, I wouldn't go implement that instead of your merge sort.