Vector Merge sort version with wrong output



I am not too sure what I did wrong in this Mergesort algorithm I made.

my output I am receiving is 4 3 5 5 4 3 8 8 8

I am speculating my int mid value could be causing this but then again I don't think it really matters as I am being consistent in merger func.



#include <iostream>
#include <vector>

using namespace std;

void merger(vector<int> &arr, int beg, int end) {

vector<int> temp;
int mid = (beg + end-1) / 2;
int right=mid+1;
int left = beg;
while (left <= mid && right <= end) {
if (arr[left] <= arr[right]) {
temp.push_back(arr[left++]);
}
else temp.push_back(arr[right++]);
}
if(left<mid){
while (left <= mid) {
temp.push_back(arr[left++]);
}
}
else{
while (right <= end) {
temp.push_back(arr[right++]);
}
}

int j = 0;
for (auto x : temp) {
arr[j++] = x;
}
// temp.clear();

}


void mergesort(vector<int> &arr, int beg, int end) {
//base case
if (beg >= end)return;
//make mid
int mid = (beg+end-1) / 2;
mergesort(arr, beg, mid);
mergesort(arr, mid+1, end);
merger(arr, beg, end);
}



int main() {

vector<int> arr1 = { 7,5,2,4,10,5,4,3,8 };

mergesort(arr1, 0, arr1.size()-1);

for (auto x : arr1) {
cout << x << " ";
}

cout << endl;

return 0;
}
```````````````````````````````````````
Put your code between CODE TAGS to retain indentation.
[code]
[/code]

In your "merger" function (which is normally called "merge"), consider where j should start.
Last edited on
Registered users can post here. Sign in or register to post.