Sorting large 1GB file with 100 millions numbers using merge sort

Question

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<iostream>
#include<fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
std::vector <long> 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<<s1<<endl;
            getline(sorted_1,line);
            s1=atol(line.c_str());
            getline(sorted_2,line2);
            s2=atol(line2.c_str());
        }
        if(s1<s2)
        {
            wynik<<s1<<endl;
            getline(sorted_1,line);
            s1=atol(line.c_str());
        }
        if(s1>s2)
        {
            wynik<<s2<<endl;
            getline(sorted_2,line2);
            s2=atol(line2.c_str());
        }
        if(sorted_1.eof())
        {
            do
            {
                wynik<<s2<<endl;
                getline(sorted_2,line2);
                s2=atol(line2.c_str());

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

        if(sorted_2.eof())
        {
            do
            {
                wynik<<s1<<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<=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 &i : vec ) { //saving into file
                sorted_piece<< i <<endl;
            }

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

for(j=0;j<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.

Answer 1

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 >> 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>> provides.

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

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

Now you can read numbers using operator>> 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 >> number) {
    sorted1Value = number;
}
if (sorted2 >> number) {
    sorted2Value = number;
}
while (sorted1 && 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 <= sorted2Value) {
        result << sorted1Value << "\n";
        sorted1 >> number;
        sorted1Value = number;
    }
    else {
        result << sorted2Value << "\n";
        sorted2 >> 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 << sorted1Value;
    result << stream1.rdbuf()
}
if (stream2) {
    result << sorted2Value;
    result << 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<char*>(&sorted1Value), sizeof(sorted1Value));

// reading
stream1.read(reinterpret_cast<char*>(&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 <long> 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 <= in the for loop is very unusual.

for(i=1;i<=25000000;i++)

Normally this is written as:

for(i = 0; i < 25000000; ++i)

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

Answer 2

Avoid std::endl

At least at first glance, it looks like you've committed the single largest sin in C++ with respect to file I/O speed: you've used std::endl where all you really wanted was a new-line ('\n').

I haven't tested your specific code, but past experience indicates that just writing '\n' instead of endl to end a line, by itself, will improve your code's speed significantly.

Maximize run size

Once you've gotten rid of premature pessimization, the next big step in making a merge sort run as fast as possible is to maximize the sizes of the individual runs you create (where a "run" is one of the intermediate files, holding a part of the input, in sorted order, which will then be merged to produce the final output).

To maximize run size, you typically start by reading in as much data as you can in the allotted amount of memory. Then, instead of fully sorting that you create a heap (e.g., with std::make_heap). Then comes the tricky part: each time you write a value to the output, you read another value from the input. You then check whether it's larger than the value you just wrote out or not. If it's larger, it can still go into the current run, so you insert it into your heap and continue.

When you encounter an item that's smaller than what's already been written out (so it can't be written to the current run) you leave the value at the top of memory, and your current heap shrinks by one item.

When your current heap is empty, you then repeat the process: build a heap of the values you read in and left at the top of memory, and start writing out the next run, reading in the next value, inserting it if possible, etc.

Assuming your input is in random order, this will typically let you approximately double the length of the intermediate runs, so you only need to do approximately half as many merge steps.

It's pretty common, however, to have input that already contains some runs of numbers in sorted order. When/if that happens, this lets you take advantage of that preexisting ordering to improve performance (to the point that if the input was already fully sorted, this will "recognize" that, and produce the fully sorted output in a single cycle of copying input to output, and it's done.

Do you really need a merge sort?

100 million integers of 4 bytes each occupy a little less than 400 megabytes of RAM. Even a fairly obsolete machine will now typically have at least 4 gigabytes of RAM, so if you just read the whole input into memory, sorted it, and wrote it out, you'd only use about 10% of the available memory. Even my semi-obsolescent (3 years old) cell phone has 3 gigabytes of RAM, so even in that case this strategy is can be entirely reasonable.

To really justify using a merge sort, we just about need to write a much more generalized sort program that can actually be used on inputs that exceed available memory. If you really do need a merge sort, my advice would be to generalize it to at least some degree--if you stick to only storing 25 million items in memory at once, that's fine--but at least process those until you reach the end of input, rather than blindly assuming there can only be 4 of them.

Answer 3

1. Don't use using namespace std; in global scope, that's a bad habit to get into. If you really dislike writing std:: over and over again then put it in function scope where needed. But even then avoid importing whole namespaces and instead only import the specific identifiers.

2. Indentation isn't consistent, this may be a copy-paste error but it is distracting.

3. Check the upper bound on the numbers. If it is less than 2 billion (2,000,000,000) then you can use int as the vector type, halving the memory requirement.

4. Why use the globals for the vector, line, filename, etc.? There is no need for that at all.

5. reserve() the vector so it doesn't need to reallocate.

6. Don't store the numbers inside the temp files as text. Parsing text is slower than reading bytes.

7. Don't use endl; that will force a flush to the output when it doesn't need to happen. Instead just write the \n.

Answer 4

Use your knowledge of the domain

You may be able to compare numbers without parsing them, by working with strings instead. First compare the sign characters (if present), then skip leading zeros, then compare the length of the significant part, and only then perform a (string) comparison.

You may be able to omit some of the above steps if you know that the numbers never have leading zeros, or are always the same sign - take advantage of the constraints you know!

If you know the maximum length of a line, you may be able to read into a fixed-size char array instead of a string in the merge phase.

Know your standard library

Instead of reimplementing merge, why not use std::merge() from <algorithm>? You need suitable input and output iterators, but those are easy to arrange.

Answer 5

Since many of the transgressions have already been described well in other answers [1] [2] , I'll resort to just enumerating the ones that immediately strike me:

• Doesn't compile on some platforms due to not including everything it uses (the string header in this case)
• Doesn't compile due to unquoted numbersSorted, 1_sorted_piece, and 2_sorted_piece
• using namespace std;
• Unnecessary globals
• Unnecessary passing of parameters by value
• Wacky and inconsistent indentation

• Somewhat poor choice of function and parameter names. e.g. I'd prefer something like

  void merge_files(std::string const& src1_filename
      , std::string const& src2_filename
      , std::string const& result_filename)
  

• Poor structuring of the code, little reuse, lots of repetition, too complex functions.
• eof checking
• Unnecessary use of std::endl
• Not reserve-ing the vector even though you know the size ahead
• Magic number (e.g. 25000000) -- If we're hardcoding this to expect exactly 100 million numbers, I'd expect to have some constant VALUE_COUNT set to the expected amount, and instead of the magic number see an expression using that constant.
  • Written in a way that's hard to parse for a human -- I'd prefer to write this value as (25 * 1000 * 1000), since it's immediately obvious that's 25 million, and any decent compiler will perform that calculation at compile time, so there's no difference in performance.

---

That said, let's look at the problem statement:

My task is to sort 1GB file with 100 million numbers using merge sort without recursion.

This looks like an excercise, so it would seem that we should stick to the requirements.

1. sort 1GB file with 100 million numbers

   This lacks some details, but we can assume it's text, with average 10 characters per number. At least one character being a separator, that gives us average 9 digits per number, so it seems quite safe to assume they're in range of a 32bit integer.

   So far so good, although your input code could have some better error handling and provide meaningful error messages when the input fails to meet your expectations.

   However I think you're being overly pessimistic with having to merge files -- as mentioned in another answer, 100 million 32bit integers take ~380 MiB, so it shouldn't be much of an issue fitting this along with a temporary buffer in the address space on much of current hardware. That being the case, I'd keep things simple, and stick with a 3 step process -- input, sorting, output.

   As such, I would expect to see at the least 3 functions, one for each of those steps.

2. using merge sort without recursion

   To me, this is asking for an iterative implementation of merge sort, and IMHO even though you made some attempt by doing 2 top level merges, you failed miserably here, as you use the standard sort on 25 million values.

   So, let's go back to how merge sort works:

   Conceptually, a merge sort works as follows:

   • Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

   • Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

   To perform this iteratively, we take the bottom-up approach. We can conceptually treat our vector of integers as a sequence of sorted sub-sequences (initially of length 1, and with the possibility of the last sub-sequence being shorter than the rest). We perform a number of merge passes, merging pairs of adjacent sub-sequences:

   • After 1 pass we have a list of sorted sub-sequences of length 2
   • After 2 passes we have a list of sorted sub-sequences of length 4
   • After 3 passes we have a list of sorted sub-sequences of length 8
   • ...

   Here I would expect to see at least a function which performs a single merge pass using given sub-sequence length, along with the main sort function which iterates the passes. Using std::merge would seem a legitimate approach -- if not, then I'm sure the implementation has already been discussed sufficiently, so there's no need to get into that.

   I think a decent implementation of a single merge pass could look something like

   template<typename InputIt, typename OutputIt>
   void merge_pass(InputIt const& src_begin
       , InputIt const& src_end
       , OutputIt const& tgt_begin
       , std::size_t step_size)
   {
       InputIt input(src_begin);
       OutputIt output(tgt_begin);
   
       std::size_t const iter_count(std::distance(src_begin, src_end) / (step_size * 2));
       for (std::size_t i(0); i < iter_count; ++i) {
           InputIt const midpoint(std::next(input, step_size));
           InputIt const endpoint(std::next(midpoint, step_size));
   
           std::merge(input, midpoint, midpoint, endpoint, output);
   
           std::advance(input, step_size * 2);
           std::advance(output, step_size * 2);
       }
   
       // Handle the remainder
       std::size_t const remaining(std::distance(input, src_end));
       if (remaining > step_size) {
           // Second block is incomplete
           InputIt const midpoint(std::next(input, step_size));
   
           std::merge(input, midpoint, midpoint, src_end, output);
       } else if (remaining > 0) {
           // Second block is missing, the rest is already sorted
           std::copy(input, src_end, output);
       }
   }
   

   The driver function could then look like

   template<typename T>
   void merge_sort(std::vector<T>& v)
   {
       uint32_t const PASS_COUNT(static_cast<uint32_t>(std::ceil(std::log2(v.size()))));
   
       std::vector<T> temp(v.size());
       for (uint32_t pass(0); pass < PASS_COUNT; ++pass) {
           merge_pass(v.begin(), v.end(), temp.begin(), 1 << pass);
           temp.swap(v); // NB: Swap is cheap
           // Now v contains sorted sub-sequences of double the size
           // and temp contains the old state, which we no longer care about
           // so we can overwrite it in the next iteration
       }
   }
   

   Benchmarking this, you'll see that this algorithm is about 2-3 times slower than standard sort. Considering the simplicity, that's quite good, and I'd consider it quite acceptable.

Live Sample on Coliru

Answer 6

Your main should be broken up into smaller functions. You have deep detail of how a step is done, then another completely different step. At this level I want an executive summary of what the step does, not the deep details. I get the feeling that the only reason you made sort_merge a function is so you can call it more than once — otherwise you would have just plowed through that implementation as well.

Have a function exist at one level of abstraction. You mentally came up with different steps. So make the code reflect that. This is hard to explain, but it's the most important lesson here.

---

void sort_merge(string result, string file1, string file2){ 

Why are you passing strings by value? There is no need to copy them.
const string& result etc.

You've been told not to use a using directive at global scope. But don't do it inside each function either! Instead, list the things you will use frequently within that cpp file (but not in a .h file), right after the #includes. E.g.

using std::string;
using std::cout;

---

s2=atol(line2.c_str());

Use the more modern functions lexical_cast instead!

auto s2= lexical_cast<long>(line2);

and you also see that you initialize where you declare! Don’t have the local variable long s1,s2; way up at the top and then first-use them later. And, define only one variable per statement.

Ah, but why read in a string and then convert to long, when the fstream can just read a long directly?

---

if (file.good() == true )

Don’t make explicit tests against true! It’s already a bool, so why do you need one more test to be sure that true == true? That's just silly. The condition takes a bool value — it does not require a top-level comparison as part of the syntax.

if ((file.good() == true ) == true)

there's no end to that! Just

if (file.good())

Or better yet, use the built-in truth test supplied to streamline this exact case:

if (file)

The eof is different in this case, but think about it: this is the normal way. You try to read and it fails. You don’t have to check for eof before reading.

Answer 7

Your basic idea is completely wrong. Splitting the file into 4 and then merging to 2 and then 1 accomplishes exactly nothing unless the parts are sorted, which you probably cannot accomplish in memory with the amount of data you have. And two-way merging is the least efficient way to merge.

This is not primarily abut coding. It is about minimizing the number of passes over the external data. It's a well-studied subject for about the last 60 years. Donald Knuth devoted volume III of The Art of Computer Programming to it. I strongly suggest that you read it,

In bald summary, you should:

1. Distribute initial runs by replacement selection.
2. Execute a balanced or polyphase merge on those files repetitively, using the standard algorithms that already exist for the purpose. Look them up.

Answer 8

Have you seen the STXXL library? This will do the sort for you much more easily, as it supports out-of core, using stxxl::sort(...). You don't have to do anything, other than load your large numbers into an appropriate container.

Answer 9

If the numbers are all unique 32-bit positive integers, you could easily sort the numbers in-memory:

1) allocate an in-memory bit array of 2^32 entries: (2^32 / 8) bytes, then clear it to zeros

2) convert each input number into a bit array index, and set the corresponding bit in the array

3) once all input numbers have been processed, output the numbers corresponding to bit array elements that are set, in order from the array

But this is probably an over-simplification of your problem !

(Strictly, the above is a "distribution / bucket sort")

Answer 10

Z-Tree is a new data structure bases on bits splitting and branching. With Z-Tree, you can sort a file of 1GB in memory with the time complexity of O(n). Much faster than merge sort.