Why my merge_sort in c++ is not working?

Question

This is my code for merge sort using vectors in c++. But it is throwing me weird result:

Result:

Input Elements: 11 33 12 44 99 34

Sorted Elements: 11 33 33 44 99 99

My Header File is nothing special: "stdafx.h"

#pragma once

#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include <iostream>
using namespace std;

Code:

#include "stdafx.h"
#include <iostream>
#include<array>
#include<vector>

//#define array_size(array) (sizeof((array))/sizeof((array[0])))

using namespace std;
template <typename T>
void merge_sort(vector<T>& arr, vector<T>& arr1, vector<T>& arr2) {
    arr.clear();
    int i = 0, j = 0, k = 0;

    for (i = 0; i < arr1.size() && j < arr2.size(); k++) {
        if (arr1.at(i) <= arr2.at(j)) {
            arr.push_back(arr1.at(i));
            i++;
        }
        else if (arr1.at(i) > arr2.at(j)) {
            arr.push_back(arr1.at(j));
            j++;
        }
        k++;
    }
    while (i < arr1.size()) {
        arr.push_back(arr1.at(i));
        i++;
    }

    while (j < arr2.size()) {
        arr.push_back(arr2.at(j));
        j++;
    }

};

template <typename T>
vector<T>merge(std::vector<T>& arr) {
    if (1 < arr.size()) {
        vector<T> arr1(arr.begin(), arr.begin() + arr.size() / 2);
        merge(arr1);//dividing to size 1

        std::vector<T> arr2(arr.begin() + arr.size() / 2, arr.end());
        merge(arr2);
        merge_sort(arr, arr1, arr2);

    }
    return (arr);
    //write_vector(arr);
};


int main()
{
    //Merge Sort

    vector<int> inputVec;
    int size = 6;

    for (int i = 0; i < size; i++) {
        int input;
        cin >> input;
        inputVec.push_back(input);
    }

    vector<int>& newSort=merge(inputVec);
    vector<int>::iterator it;
    for (it = newSort.begin(); it != newSort.end(); ++it)
        cout<<endl<< *it << endl;
    return 0;
}

Result Window: My Output Can some one please point out what is wrong? Why it creates duplicate elements?

It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: **[How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/)** — NathanOliver, Aug 30 '16 at 16:03
`vector& newSort=merge(inputVec);` MS VS? This is illegal C++ code. — Slava, Aug 30 '16 at 16:06
The right tool to solve such problems is your debugger. You should step through your code line-by-line *before* asking on Stack Overflow. For more help, please read [How to debug small programs (by Eric Lippert)](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). At a minimum, you should \[edit] your question to include a [Minimal, Complete, and Verifiable](http://stackoverflow.com/help/mcve) example that reproduces your problem, along with the observations you made in the debugger. — πάντα ῥεῖ, Aug 30 '16 at 16:06
@BiagioFesta do not quite understand your comment. Do you agree? — Slava, Aug 30 '16 at 16:09
@Slava You're right! I agree with you. Anyway there so many things wrong with that code. I don't know where to start — BiagioF, Aug 30 '16 at 16:10
Read the for-loop carefully, paying special attention to which of the inputs you're merging into the result. (BTW: the second condition in that loop is unnecessary, as it's always true when the first is false.) — molbdnilo, Aug 30 '16 at 16:15
Your example isn't complete - either provide your `stdafx.h` and `merger.h` or remove their includes. — Toby Speight, Aug 30 '16 at 16:38
@molbdnilo dont worry about the header files, I am not using that at present in my code, I thought of defining the class for the merging, but as it was reporting more errors, so I got everything on the main. — blackmamba591, Sep 02 '16 at 15:24
@ArunavaNag in C++ you cannot assign rvalue to lvalue reference, though MS VS has extention that allows that. So as this is not standard it is not clear if lvalue reference extends lifetime of temporary or not. You better not use such code at all. — Slava, Sep 02 '16 at 15:29
@Slava could you please provide me any link that I can read more about what you are saying? — blackmamba591, Sep 02 '16 at 15:30
@ArunavaNag Read here http://stackoverflow.com/questions/11508607/rvalue-to-lvalue-conversion-visual-studio — Slava, Sep 02 '16 at 15:32

score 0 · Accepted Answer · answered Aug 30 '16 at 16:26

See your code in merge_sort function:

for (i = 0; i < arr1.size() && j < arr2.size(); k++) {
    if (arr1.at(i) <= arr2.at(j)) {
        arr.push_back(arr1.at(i));
        i++;
    }
    else if (arr1.at(i) > arr2.at(j)) {
        arr.push_back(arr1.at(j));
        //            ^^^^
        // It should be arr.push_back(arr2.at(j));
        j++;
    }
    k++;
}

Replace the arr.push_back(arr1.at(j)); with arr.push_back(arr2.at(j)); and your code will work like a charm.

Why my merge_sort in c++ is not working?

1 Answers1