Sorting large 1GB file with 100 millions numbers using merge sort My task is to sort 1GB file with 100 million numbers using merge sort without recursion. My idea is to split file into 4 pieces, then to 2 and at the end to one file.

#include&lt;iostream&gt;
#include&lt;fstream&gt;
#include &lt;cstdlib&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
using namespace std;
std::vector &lt;long&gt; vec;

int i=0,numberOfpieces=0;
string line,filename;

//sorting and merge 2 files
void sort_merge(string result, string file1, string file2){ 

fstream wynik((result+".txt"), std::ios::out);

    string line, line2;
    long s1,s2;
    fstream sorted_1,sorted_2;
    sorted_1.open(file1+".txt");
    sorted_2.open(file2+".txt");

    getline(sorted_1,line);
    s1=atol(line.c_str());
    getline(sorted_2,line2);
    s2=atol(line2.c_str());

    do
    {
        if(s1==s2)
        {
            wynik&lt;&lt;s1&lt;&lt;endl;
            getline(sorted_1,line);
            s1=atol(line.c_str());
            getline(sorted_2,line2);
            s2=atol(line2.c_str());
        }
        if(s1&lt;s2)
        {
            wynik&lt;&lt;s1&lt;&lt;endl;
            getline(sorted_1,line);
            s1=atol(line.c_str());
        }
        if(s1&gt;s2)
        {
            wynik&lt;&lt;s2&lt;&lt;endl;
            getline(sorted_2,line2);
            s2=atol(line2.c_str());
        }
        if(sorted_1.eof())
        {
            do
            {
                wynik&lt;&lt;s2&lt;&lt;endl;
                getline(sorted_2,line2);
                s2=atol(line2.c_str());

            }
            while(!sorted_2.eof());
            break;
        }

        if(sorted_2.eof())
        {
            do
            {
                wynik&lt;&lt;s1&lt;&lt;endl;
                getline(sorted_1,line);
                s1=atol(line.c_str());
            }
            while(!sorted_1.eof());
        }

    }
    while (!sorted_1.eof() ||!sorted_2.eof());}


int main()
{
    fstream file;
    file.open("file.txt");
    if (file.good() == true )
    {
        do
        {
            for(i=1;i&lt;=25000000;i++){ //splittining file into 4 pieces
            getline(file,line);
            vec.push_back(atol(line.c_str()));
            if(file.eof()){ //in case of last piece when quantity of numbers is less than 50
                break;
            }
            }
            sort(vec.begin(), vec.end() );//sorting vector
            std::string nm = std::to_string(numberOfpieces); //creating indyvidual name for piece
            filename="sorted_piece_"+nm+".txt";
            fstream sorted_piece(filename, std::ios::out);

            for ( auto &amp;i : vec ) { //saving into file
                sorted_piece&lt;&lt; i &lt;&lt;endl;
            }

            numberOfpieces++;
            vec.clear();
        }
        while ( !file.eof() );
    }
string outFile;
string sorted1;
string sorted2;
int j=0,counti=0;

for(j=0;j&lt;numberOfpieces;j+=2){//merging into 2 pieces
    std::string j1 = std::to_string(j);
    std::string j2 = std::to_string(j+1);
    std::string c = std::to_string(counti);
    outFile=c+"_sorted_piece";
    sorted1="sorted_piece_"+j1;
    sorted2="sorted_piece_"+j2;
    sort_merge(outFile,sorted1,sorted2);
    counti++;
}
outFile=numbersSorted;
sorted1=1_sorted_piece;
sorted2=2_sorted_piece;
sort_merge(outFile,sorted1,sorted2);//merging into 1 piece

return 0;
}


Unfortunately it is slow and I don't know exactly what is the best way to improve it, because vector sorting has \$O(nlog(n))\$ complexity. Also, my algorithm with merging 2 files have \$O(n)\$ complexity. Maybe splitting into files takes too much time, but I can't hold vectors that are too long in RAM.
Don't do this

using namespace std;


This is a bad habit that will get you into a lot of trouble. Please break the habit before it becomes ingrained.

see: Why is “using namespace std” considered bad practice?

Note: The reason the "standard" library uses the namespace std:: is so that it is not a large burden to use as a prefix.

Prefer '\n' over std::endl

Others have mentioned it.
The problem is that std::endl performs a flush of the stream (in addition to adding '\n') as a result this makes using the stream very inefficient as you need to wait to write every value to disk before continuing.

Let the system flush its own internal buffer at the optimum time. It will do this automatically without any of your help.

Reading Value

I see that you are not using the standard stream to integer conversion.

long value;
stream &gt;&gt; value;


but rather using the line reader than using atol() to convert the string into a number.

I assume you have done the appropriate speed tests and found this to be faster on the scale that you are using and you don't need all the facilities that the stream operator&gt;&gt; provides.

If this is true then I would wrap up that call so that you can use atol() and operator&gt;&gt; to make your code more readable.

struct Number
{
    long value;
    static std::string  reusableBuffer;
    operator long() const {return value;}
    friend std::istream&amp; operator&gt;&gt;(std::istream&amp; str, Number&amp; data) {
        std::getline(str, data.reusableBuffer);
        data.value = std::atol(data.reusableBuffer);
        return str;
    }
};


Now you can read numbers using operator&gt;&gt; but still have the speed you have verified with atol().

Never test for eof in a loop

while (!sorted_1.eof() ||!sorted_2.eof());}


The problem becomes that if there is an error on the stream then you end up going into an infinite loop (if there is an error reading from the stream it goes into a bad state until you  reset it. While in a bad state it will refuse to read any more values and thus never reach the end of the file.

Rather than testing for eof() you should check to make sure the stream is good() (if it reaches eof() or error() then it will no longer be good() so your loop will still exit correctly).

The easy way to test for good() is to simply use the stream in a boolean context (an expression that is expected to be bool) and the compiler will convert the stream to bool which results in a call to good().

while(sorted_1 || sorted_2);


Merge I think can be simplified.

I think we can simplify that merge algorithm a lot.

Number number;
if (sorted1 &gt;&gt; number) {
    sorted1Value = number;
}
if (sorted2 &gt;&gt; number) {
    sorted2Value = number;
}
while (sorted1 &amp;&amp; sorted2) {
    // Don't need to explicitly test if they are equal.
    // If they are equal always use the sorted1 file.
    // that way you get a stable sort (an important property for
    // sorted values in some situations).
    //
    // It also makes the code simpler.
    if (sorted1Value &lt;= sorted2Value) {
        result &lt;&lt; sorted1Value &lt;&lt; "\n";
        sorted1 &gt;&gt; number;
        sorted1Value = number;
    }
    else {
        result &lt;&lt; sorted2Value &lt;&lt; "\n";
        sorted2 &gt;&gt; number;
        sorted2Value = number;
    }
}
// At this point one of the streams is empty.


Copy one file to another.

When you have merged all the values out of one file. Then the remaining numbers from the other file are simply copied to the destination. But there is no need to spend extra time converting those numbers from text to an integer then back into text. Simply copy the raw data from one file to the other.

// At this point one of the streams is empty.
if (stream1) {
    result &lt;&lt; sorted1Value;
    result &lt;&lt; stream1.rdbuf()
}
if (stream2) {
    result &lt;&lt; sorted2Value;
    result &lt;&lt; stream2.rdbuf()
}


Intermediate format

So the intermediate files don't need to be in human readable form. You spend a lot of time converting integers to and from text. Rather than doing this you could write the binary representation of the number to an intermediate file and then read it directly back into the number when merging.

// writing
result.write(reinterpret_cast&lt;char*&gt;(&amp;sorted1Value), sizeof(sorted1Value));

// reading
stream1.read(reinterpret_cast&lt;char*&gt;(&amp;sorted1Value), sizeof(sorted1Value));


Merging more than one file.

Currently you perform the merge operation 3 times. Once to merge parts 1 and 2 into a temp file. Then you merge 3 and 4 into a second temp file and finally you merge the temp files into the output.

Merging from different streams is not that memory intensive. So you should read from all the temporary files at the same time (within reason as long as you have less than a thousand part file).

So you should open all 4 temp files and read the values from them. Each iteration find the largest value from each of the 4 files write that to the output and read the next value.

Global State.

Global state

std::vector &lt;long&gt; vec;

int i=0,numberOfpieces=0;
string line,filename;


Is always considered a bad thing. Never use it. You can still get the same efficiencies by using local values in the appropriate places.

One thing you way want to do to increase the efficiency of std::vector is to reserve its size. That way it never needs to do any reallocation (which is expensive).

vec.reserve(25000000);


Note your use of &lt;= in the for loop is very unusual.

for(i=1;i&lt;=25000000;i++)


Normally this is written as:

for(i = 0; i &lt; 25000000; ++i)


This is because indexes into arrays (vectors) always start at zero.