C++ Merge Sort Implementation

Question

Edit: A follow up question can be found here.

---

My first try at mergesort, without resorting to any references:

#include <iostream>
#include <vector>

std::vector<int> Merge(std::vector<int>, std::vector<int>);
std::vector<int> MergeSort(std::vector<int>);

int main()
{
    // No need to review this, it was just for testing purposes
    std::vector<int> a;
    for (int i = 0; i < 100; i++) {
        a.push_back(6000.0 * rand() / RAND_MAX);
    }
    for (int i = 0; i < a.size(); i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
    a = MergeSort(a);
    for (int i = 0; i < a.size(); i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
    return 0;
}

std::vector<int> Merge(std::vector<int> arr1, std::vector<int> arr2) {
    int size1 = arr1.size();
    int size2 = arr2.size();
    std::vector<int> res(size1 + size2, 0);
    int i1 = 0;
    int i2 = 0;
    while (i1 < size1 && i2 < size2) {
        if (arr1[i1] < arr2[i2]) {
            res[i1 + i2] = arr1[i1];
            i1++;
        }
        else {
            res[i1 + i2] = arr2[i2];
            i2++;
        }
    }
    while (i1 < size1) {
        res[i1 + i2] = arr1[i1];
        i1++;
    }
    while (i2 < size2) {
        res[i1 + i2] = arr2[i2];
        i2++;
    }
    return res;
}

std::vector<int> MergeSort(std::vector<int> arr) {
    if (arr.size() < 2) {
        return arr;
    }
    else if (arr.size() == 2) {
        // If array is of size 2, return it sorted
        if (arr[0] > arr[1]) {
            arr[1] += arr[0];
            arr[0] = arr[1] - arr[0];
            arr[1] -= arr[0];
        }
        return arr;
    }
    else {
        // Recursively split in halves until all vectors are size 1 or 2, then merge
        return Merge(
            MergeSort(std::vector<int>(arr.begin(), arr.begin() + arr.size() / 2)),
            MergeSort(std::vector<int>(arr.begin() + arr.size() / 2, arr.end()))
        );
    }
}

A few questions:

1. Have I implemented a merge sort correctly? Or is it some other sort?
2. How can I make it work for multiple data types rather than just int?
3. I imagine it's not very efficient (I don't know much about std::vector<T>.begin or std::vector<T>.end), how could I make it more efficient?

Answer 1

Your big mistake is not using iterators.

As a result you pass your vectors by value, which causes the vectors to be copied a lot.

std::vector<int> MergeSort(std::vector<int> arr)
                                            ^^^    A copy of the array is made when you call this function.


std::vector<int> Merge(std::vector<int> arr1, std::vector<int> arr2)
                                        ^^^^ Copy              ^^^^ Copy

Now, you could mitigate this by passing the values by reference. But I think a better solution is to pass iterators into the container. That way you also allow for other container types.

Luckily for you, a return is a move, not a copy - so that is not as big a problem as a copy.

template<typename I>
void MergeSort(I begin, I end)

template<typename I,
void Merge(I src1Begin, I src1End, I src2Begin, I src2End, I dstBegin);

Answer 2

1. Yes, it's a mergesort, switching to something else for small ranges is a common refinement.

   Be aware your implementation is not stable, though it doesn't matter for int on your machine.
   You can easily address that at no extra cost.

   Change: if (arr1[i1] < arr2[i2]) into if (arr1[i1] <= arr2[i2])

2. Use templates, for the inputs type and an optional comparison-predicate.
   Though you should first change it to work with iterators, modifying the passed range, to increase flexibility and reduce the number of instantiations needed.

3. The most important thing you can do to make it more efficient is reducing the number of allocations and deallocations. It should suffice to allocate just one auxiliary array over the runtime of the whole algorithm.

---

1. Use using std::swap; swap(a, b); if you need to swap two objects, don't roll your own. Thus your code will be:

   • More idiomatic and readable.
   • Possibly more efficient.
   • Avoiding common pitfalls. Bit-hacks often fail on self-swap (which is not an issue for you) or invoke undefined behavior if carelessly implemented (signed integer-overflow is UB).

2. Don't bother with an else-branch if the conditional block ends with a return/break/... . Best to minimize nesting.

3. Use move-semantics (C++11) to avoid costly copies.

4. If you want to stream a single character, don't use a length-1-string but a character. It's more efficient.

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

6. As an aside, I really don't like single-statements-blocks. Others differ.

7. You know that rand() is a really poor RNG? Look into <random> (C++11) for better choices. And rand() should be seeded (once and only once) with srand() unless you need repeatability. So, your use is actually defensible, though you should call it out in a comment, maybe with // srand(1);.

8. Many of your while-loops should be for-loops. Using the proper loop makes compreheending the code easier.

Answer 3

Some optimizations:

1. You are calling arr.size() in MergeSort(..) many times, you can store it in a local variable.

Answer 4

1. It's a merge sort al right.

2. templates,

   template<T>
   std::vector<T> Merge(std::vector<T> arr1, std::vector<T> arr2)
   
   template<T>
   std::vector<T> MergeSort(std::vector<T> arr)
   

   and then replace every usage of int that isn't for size or index with T

   Having said that you can also create a version that takes 2 iterators the begin and end)

3. You can make it more efficient by not allocating as much. Every time you fill a vector it needs to allocate a buffer to put the values in. Allocation is not free.

Instead you can provide the target buffer. However that means having to keep track of which way to copy the data and tends to get complicated.

I prefer the bottom up merge sort where separate the input into chunks of length n then merge 2 chunks pairwise then multiply n by 2 and repeat.