Below is my implementation of merge sort in C++. I have taken a small input size just for convenience in debugging. The merge sort code is still not working after rectifying a little mistake which resulted in an std::out_of_range exception being thrown.
#include <iostream>
#include <chrono>
#include <fstream>
#include <vector>
using namespace std;
using namespace std::chrono;
void mergeSort(vector<long>, long, long);
void merge(vector<long>, long, long, long);
void sortf(long);
void print(long);
void print(long n) //prints n random numbers in a file
{
ofstream of("List.txt");
long i;
for (i = 0; i < n; i++)
{
long x = rand() % n + 1;
of << x << endl;
}
of.close();
}
void sortf(long x) //calls the merge sort function and sends it array of elements which
{ //were previously stored in the file and outputs sorted values to another file
vector<long> arr;
ifstream f("List.txt");
long i = 0;
long line;
while (i < x)
{
f >> line;
arr.push_back(line);
i++;
}
high_resolution_clock::time_point t1 = high_resolution_clock::now();
long len = arr.size() - 1;
mergeSort(arr, 0, len); //calls merge sort
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto duration = duration_cast<nanoseconds>(t2 - t1).count();
cout << "\nTime taken:\n" << duration << " nanoseconds.\n"; //outputs time taken
ofstream of("ListOut3.txt");
for (i = 0; i < x; i++)
{
cout << arr.at(i) << endl;
}
for (i = 0; i < x; i++)
{
of << arr.at(i) << endl;
}
}
void mergeSort(vector<long> arr, long l, long r)
{
long n = arr.size();
if (l >= r) //Base condition to stop recursion
{
return;
}
long mid = (l + r) / 2; //calculates mid position for partitioning
mergeSort(arr, l, mid);
mergeSort(arr, (mid + 1), r);
merge(arr, l, mid, r);
}
void merge(vector<long> arr, long l, long mid, long r) //applies merging
{
vector<long> lv;
vector<long> rv;
int p;
for (p = l; p < mid; p++)
{
lv.push_back(arr.at(p));
}
for (p = mid; p < r; p++)
{
rv.push_back(arr.at(p)); //Error Solved
}
long l1 = lv.size();
long l2 = rv.size();
long i = 0, j = 0, k = 0;
while (i < l1 && j < l2)
{
if (lv.at(i) < rv.at(j))
{
arr.at(k) = lv.at(i);
i++;
}
else
{
arr.at(k) = rv.at(j);
j++;
}
k++;
}
while (i < l1)
{
arr.at(k) = lv.at(i);
k++;
i++;
}
while (j < l2)
{
arr.at(k) = rv.at(j);
k++;
j++;
}
}
int main()
{
long n = 4;
print(n); //printing n numbers in the file
sortf(n);
}
The exact output of the program is:
Time taken:
6897 nanoseconds.
4
3
2
4
Please help me figure out the cause since I am new to STL and vectors.
Changed the code so that the vector was passed by reference. Now it working correctly and giving the desired output. Below is the correct, working solution:
#include <iostream>
#include <cstdlib>
#include <chrono>
#include <fstream>
#include <array>
#include <vector>
using namespace std;
using namespace std::chrono;
void mergeSort(vector<long>&, long, long);
void merge(vector<long>&, long, long, long);
void sortf(long);
void print(long);
void print(long n) //prints n random numbers in a file
{
ofstream of("List.txt");
long i;
for (i = 0; i < n; i++)
{
long x = rand() % n + 1;
of << x << endl;
}
of.close();
}
void sortf(long x) //calls the merge sort function and sends it array of elements which
{ //were previously stored in the file and outputs sorted values to another file
vector<long> arr;
ifstream f("List.txt");
long i = 0;
long line;
while (i < x)
{
f >> line;
arr.push_back(line);
i++;
}
high_resolution_clock::time_point t1 = high_resolution_clock::now();
long len = arr.size() - 1;
mergeSort(arr, 0, len); //calls merge sort
high_resolution_clock::time_point t2 = high_resolution_clock::now();
auto duration = duration_cast<nanoseconds>(t2 - t1).count();
cout << "\nTime taken:\n" << duration << " nanoseconds.\n"; //outputs time taken
ofstream of("ListOut3.txt");
for (i = 0; i < x; i++)
{
cout << arr.at(i) << endl;
}
for (i = 0; i < x; i++)
{
of << arr.at(i) << endl;
}
}
void mergeSort(vector<long> &arr, long l, long r)
{
if (l >= r) //Base condition to stop recursion
{
return;
}
long mid = (l + r) / 2; //calculates mid position for partitioning
mergeSort(arr, l, mid);
mergeSort(arr, (mid + 1), r);
merge(arr, l, mid, r);
}
void merge(vector<long> &arr, long l, long mid, long r) //applies merge sort algorithm
{
vector<long> lv;
vector<long> rv;
int p;
for (p = l; p <= mid; p++)
{
lv.push_back(arr.at(p));
}
for (p = mid+1; p <= r; p++)
{
rv.push_back(arr.at(p));
}
long l1 = lv.size();
long l2 = rv.size();
long i = 0, j = 0, k = l;
while (i < l1 && j < l2)
{
if (lv.at(i) < rv.at(j))
{
arr.at(k) = lv.at(i);
i++;
}
else
{
arr.at(k) = rv.at(j);
j++;
}
k++;
}
while (i < l1)
{
arr.at(k) = lv.at(i);
k++;
i++;
}
while (j < l2)
{
arr.at(k) = rv.at(j);
k++;
j++;
}
}
int main()
{
long n = 60;
print(n); //printing n numbers in the file
sortf(n);
}