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:
- Have I implemented a merge sort correctly? Or is it some other sort?
- How can I make it work for multiple data types rather than just
int
? - I imagine it's not very efficient (I don't know much about
std::vector<T>.begin
orstd::vector<T>.end
), how could I make it more efficient?
x ^= y; y ^= x; x ^= y;
\$\endgroup\$