Implementation of merge sort algorithm in C++

This is my implementation of "merge sort" in C++. I'm still a newbie at C++ so:

• Have I understood how merge sort works and implemented it in the right way?

• Have I used any bad practices?

• How could the code be improved upon in terms of efficiency?

Criticism is welcome and appreciated!

#include 
#include 
#include 
#include 
using namespace std;

vector merge(vector firstHalf, vector secondHalf){
    vector combined;
    for(int i = firstHalf.size() + secondHalf.size(); i > 0;  i--){//merge two vectors
        if(firstHalf.back() > secondHalf.back() && !firstHalf.empty()){
            combined.push_back(firstHalf.back());
            firstHalf.pop_back();
        }else if(!secondHalf.empty()){
            combined.push_back(secondHalf.back());
            secondHalf.pop_back();
        }
    }
    vector revCombined;//reverse merged vectors. Vectors don't have pop_front and I didn't want to use lists.

    for(int i = 0; i  mergeSort(vector &inputArray){//for example [9, 8, 1] as input
    if(inputArray.size() > 1){
        vector firstHalf;
        vector secondHalf;

        for(int i = 0; i  split(string str, char delimiter) {
    vector internal;
    stringstream ss(str); // Turn the string into a stream.
    string tok;

    while(getline(ss, tok, delimiter)) {
        internal.push_back(tok);
    }

    return internal;
}
vector floatVectorInput(){
    string inputString;
    getline(cin, inputString);

    vector stringArray = split(inputString, ' ');

    vector array; 
    for(int i = 0; i  inputArray = floatVectorInput();

    vector sorted = mergeSort(inputArray);

    cout << endl << "Sorted Array:" << endl;    
    for(int i = 0; i < sorted.size(); i++){
        cout << sorted[i];
        if(i == sorted.size()-1){
            cout << endl << endl;
        }else{
            cout << ", ";
        }
    }
    return 0;
}

merge calls back() on empty vector

The logic in your merge function has a bug.

if (firstHalf.back() > secondHalf.back() && !firstHalf.empty()) { … }

The first problem is that you access firstHalf.back() before the check that !firstHalf.empty(). The checks should be in reversed order.

The second problem is that you're also accessing secondHalf.back() without checking whether !secondHalf.empty().

While the code could be fixed with less changes, I suggest that you look at the problem again: Merging only really makes sense if neither of the halves is empty. So let's break the problem into two parts:

• Merge two non-empty containers.

• Append the remaining elements to the already merged container.

std::vector combined{};
// Merge two non-empty containers.
while (!firstHalf.empty() && !secondHalf.empty()) {
    if (firstHalf.back() > secondHalf.back()) {
        combined.push_back(firstHalf.back());
        firstHalf.pop_back();
    } else {
        combined.push_back(secondHalf.back());
        secondHalf.pop_back();
    }
}
// Append the remaining elements to the already merged container.
while (!firstHalf.empty()) {
    combined.push_back(firstHalf.back());
    firstHalf.pop_back();
}
while (!secondHalf.empty()) {
    combined.push_back(secondHalf.back());
    secondHalf.pop_back();
}

This version is not only correct but also simpler to understand.

Input does not handle excess spaces correctly

If you feed your program with input that puts more than one space between two numbers, your program will crash.

While it is a legitimate choice to require exactly one space between subsequent numbers, it turns out that you can make the behavior more user-friendly and simplify the code at the same time.

std::vector floatVectorInput()
{
    std::vector numbers{}; 
    std::string line{};
    std::getline(std::cin, line);
    std::istringstream iss{line};
    float x;
    while (iss >> x) {
        numbers.push_back(x);
    }
    if (!iss.eof()) {
        throw std::runtime_error{"Garbage input"};
    }
    return numbers;   
}

Instead of first splitting into a vector of strings, I'm reading the floats from the std::istringstream directly. This will skip over any amount of white-space as desired.

The !iss.eof() check is there because I want to make sure that we stop because the input is exhausted, not because there was something that is not a floating-point number.

Avoid using namespace std

I know that many C++ tutorials want you to put

using namespace std;

into every file. I don't think that this is good advice and recommend against doing it. Importing namespaces is a complex operation and you probably don't understand all its implications. For example, what will the following code print with and without the using namespace std;?

#include 
#include 

//using namespace std;

void swap(double x, double y)
{
  std::clog << "swap(" << x << ", " << y << ")\n";
}

int main()
{
  int a = 1;
  int b = 2;
  swap(a, b);
  swap(3, 4);
}

With the offending line commented out, the code will print swap(1, 2) and swap(3, 4) as you'd probably expect. However, with using namespace std, it will only print the second line.

What happened?


By using namespace std, we've made std::swap (defined in `) visible. Since our own swap takes doubles as parameters, calling it with an argument of type int is not a perfect match. What the C++ compiler does is adding an implicit conversion from int to double. However, if there is also a function that doesn't require this conversion to happen, the compiler will prefer it. It just so happens that std::swap is a template that will be a better match in this case. So why is only the first call resolved to std::swap then? This is because std::swap takes its arguments as mutable references. A temporary object (like an integer literal in this case) doesn't bind to a mutable reference.

I understand that this is complicated stuff for a beginner and you probably shouldn't have to worry about it at this point. But if you're using namespace std, you'll have to know it or you won't understand your code.

That said, using namespace std is also frowned upon in production-quality code (written by people who ought to understand the aforementioned language rules) so you're teaching yourself a bad habit by using it. Just be explicit and prefix symbols from the standard library with std::. It will tell the reader at a glance where the symbol comes from which makes understanding the code easier for readers of any level of experience.

Be const correct

Your mergeSort function doesn't modify its argument (sorts the vector in-place) but actually returns a new, sorted vector. Therefore, make its argument const`.

std::vector mergeSort(const std::vector& inputArray);
//                           ^^^^^

You should do this with any variable that you don't intend to modify.

Use the correct

StackExchange Code Review Q#153239, answer score: 4