Search code examples
c++exceptionvectorstlmergesort

std::out_of_range exception thrown in C++ Merge sort implementation


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.


Solution

  • 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);
    }