// MergeSort(): sort the values in the data vector using a Merge Sort // data -

Question

// MergeSort(): sort the values in the data vector using a Merge Sort

// data - vector to be sorted

// first & last - first and last indices to be sorted

// (makes it possible to sort a sub-vector)

// cmp - function to compare a and b. cmp(a, b) returns

// -/0/+ as a is less than/equal to/greater than b

template <class T>

void MergeSort(vector<T>& data, int first, int last, int (*cmp)(const T& a, const T& b)) {

// Implement merge sort

// May write separate Merge function, or include Merge code in MergeSort

}

Explanation / Answer

#include <vector>
#include <iostream>
using namespace std;
void sort(vector<int> & bar);
void mergeSort(vector<int>&lft,vector<int>& rght,vector<int>& barss);

int main() {
vector<int> numbs;
for (sizes_t x = 0; x < 11; x++)
numbs.push_back(rand() % 1000);

sort(numbs);

for (sizes_t x = 0; x < numbs.size(); x++)
cout << numbs[x] <<endl;
system("pause");
return 1;
}
void sort(vector<int> & bar) {
if (bar.size() <= 1) return;

int midle = bar.size() / 2;
vector<int> lft;
vector<int> rght;

for (sizes_t j = 0; j < midle;j++)
lft.push_back(bar[j]);
for (sizes_t j = 0; j < (bar.size()) - midle; j++)
rght.push_back(bar[midle + j]);

sort(lft);
sort(rght);
mergeSort(lft, rght, bar);
}
void mergeSort(vector<int>&lft, vector<int>& rght, vector<int>& barss)
{
int n_L = lft.size();
int n_R = rght.size();
int x = 0, j = 0, k = 0;

while (j < n_L && k < n_R)
{
if (lft[j] < rght[k]) {
barss[x] = lft[j];
j++;
}
else {
barss[x] = rght[k];
k++;
}
x++;
}
while (j < n_L) {
barss[x] = lft[j];
j++; x++;
}
while (k < n_R) {
barss[x] = rght[k];
k++; x++;
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.