31
\$\begingroup\$

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.

\$\endgroup\$
  • 7
    \$\begingroup\$ did you profile to see where the slow part is? a poor mans profiler would be to add some stdout<<"doing step x"; every 50k numbers when reading and then after the sort then every 50k numbers when writing, ... \$\endgroup\$ – ratchet freak Jun 21 '17 at 13:48
  • 7
    \$\begingroup\$ Are you intentionally "re-implementing the wheel" or can you just invoke the standard sort utility to meet your needs? \$\endgroup\$ – Toby Speight Jun 21 '17 at 16:28
  • \$\begingroup\$ @TobySpeight, it seems like the whole vector cannot be hold in memory. Though paring that with std::merge would work. \$\endgroup\$ – Incomputable Jun 21 '17 at 21:50
  • 2
    \$\begingroup\$ the first problem might be storing a lot of numbers in text. Storing in binary will be much smaller and faster to process \$\endgroup\$ – phuclv Jun 22 '17 at 4:27
  • 2
    \$\begingroup\$ To add to @TobySpeight's point, generating a test file with time shuf -r -i 0-2000000000 -n 100000000 > intshuf.txt took 15s and sorting it with time sort -n intshuf.txt > intsort.txt took 107s on a VM on my laptop. This might be a good benchmark to compare your code against. \$\endgroup\$ – Digital Trauma Jun 22 '17 at 23:50

10 Answers 10

5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ No don't add using clause after the includes. Prefer to do it within the function in as closes scope as possible. But prefer to use the full prefix std:: \$\endgroup\$ – Martin York Jun 22 '17 at 7:02
  • 1
    \$\begingroup\$ More modern lexical_cast<>! Lexical cast is not part of the standard and it more dated than the modern standard version std:: strtol(). So maybe the advice should be use std::strtol() rather than the dated std::atol() \$\endgroup\$ – Martin York Jun 22 '17 at 7:04
  • \$\begingroup\$ @LokiAstari sorry, I thought it was by now. Actually, I think I'd just stream in from the file, rather than reading a string and then converting. strtol is unfriendly toward templates, and making the datum type abstracted is a good progression for this problem. \$\endgroup\$ – JDługosz Jun 22 '17 at 8:12
  • \$\begingroup\$ That paper was from 2006. It did not make it into C++11 and I have not heard anything about putting it in a subsequent version. The lexical_cast<> seems to have fallen out of popularity in favor of the more Java like std::to_string() and std::stoX() \$\endgroup\$ – Martin York Jun 22 '17 at 18:06
-1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. (BTW we see your identical answer on Stack Overflow) \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 12 '17 at 0:01
  • \$\begingroup\$ Z-Tree is a complex new data structure. Document, code, demo and screenshots are needed to understand it. It is not easy to describe the essential parts of it in this post. \$\endgroup\$ – Pegasus Sep 12 '17 at 0:13
  • \$\begingroup\$ This answer is not quite up to Code Review's quality standards, but potentially salvageable. It is worth noting that Z-Tree is not a comparison-based sort. Also, noting that the Z-Tree technique is documented in abandoned US patent application 20140222870 should be a sufficiently reliable citation that does not rely on any single hosting service. \$\endgroup\$ – 200_success Sep 12 '17 at 0:32
  • \$\begingroup\$ IAC, that’s not O(n). The page describes a hash trie with nonbranching nodes collapsed. So it’s n log₂(n) for good hash keys and degenerates to n² in the pathological case. \$\endgroup\$ – JDługosz Apr 5 '18 at 3:07
1
\$\begingroup\$

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")

\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
54
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ About he "copy one file to another": I fully agree with the approach, but there is no need to output a '\n' before the rdbuf(), as the first character in the rdbuf() will be a '\n' as well. Not that two newlines in a row will do any harm, though. \$\endgroup\$ – Sjoerd Jun 23 '17 at 4:01
  • \$\begingroup\$ @Sjoerd. You are correct. That's the problem with code snipets that you don't test. I have fixed. \$\endgroup\$ – Martin York Jun 23 '17 at 15:34
  • \$\begingroup\$ The "Reading Value" section reads like a passive aggressive way of saying "just use stream formatters". I like it :) \$\endgroup\$ – Lightness Races with Monica Jun 26 '17 at 11:38
  • \$\begingroup\$ "Global state is always considered a bad thing [..] Never use it" We should not use std::cout then? \$\endgroup\$ – Lightness Races with Monica Jun 26 '17 at 11:39
  • \$\begingroup\$ @BoundaryImposition there are always exceptions to a rule. But as a general rule global mutable state is always (usually) a bad thing. Also why would you use std::cout in a real application? User side code would have a GUI, server side code would print to the logging system. Which leaves toy programs and unix tools. \$\endgroup\$ – Martin York Jun 26 '17 at 17:34
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. \$\endgroup\$ – Toby Speight Sep 7 '17 at 16:36
1
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Your assertions contradict other answers. «probably cannot accomplish in memory with the amount of data you have» is clearly wrong. «accomplishes exactly nothing» is wrong if that first statement were true! \$\endgroup\$ – JDługosz Jun 22 '17 at 5:48
  • 2
    \$\begingroup\$ 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. 100 million is not that many. Even longs this is only about 0.7G given the size of memory on modern machines this is not much of a stretch. Now when I sort 2.2 trillion numbers that becomes an issue. uncompressed 16 TBytes but we store it compressed so about 8 TBytes a column. \$\endgroup\$ – Martin York Jun 22 '17 at 7:10
  • \$\begingroup\$ @Loki, it's all relative. On a lightly-loaded modern workstation or server, the sizes are comfortable, but on a small device (such as a music player or process controller) you may need to be more creative. And there's always educational value in dealing with constraints. \$\endgroup\$ – Toby Speight Jun 22 '17 at 7:49
  • \$\begingroup\$ @TobySpeight Quite true, but what's the likelihood of having to sort 100 million numbers by non-recursive merge sort on such a small device, especially when that's not explicitly stated in the problem statement. IMHO this is an excercise, and the main point is a non-recursive merge sort, so it should at least achieve some basic in-memory implementation of that. \$\endgroup\$ – Dan Mašek Jun 26 '17 at 1:52
45
\$\begingroup\$

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.

\$\endgroup\$
  • 8
    \$\begingroup\$ Writting\n instead of endl, speed up sorting 3 times - from 1000s to 350s Thanks for advice :) \$\endgroup\$ – Adrian Jun 21 '17 at 14:52
  • 5
    \$\begingroup\$ @Adrian Calling std::ios::sync_with_stdio(false); at the start of your program can also make a huge difference in some cases. \$\endgroup\$ – Viktor Dahl Jun 21 '17 at 18:57
  • 4
    \$\begingroup\$ @ViktorDahl That only applies when using std::cin and std::cout here we are using files std::ifstream and std::ofstream. \$\endgroup\$ – Martin York Jun 21 '17 at 19:08
  • 19
    \$\begingroup\$ Re 400 megabytes being small: boy have things changed since Knuth! \$\endgroup\$ – JDługosz Jun 22 '17 at 5:38
  • 3
    \$\begingroup\$ As to why \n vs. endl is important: the latter flushes the output stream, which forces frequent communication to the disk/network/what-have-you. These other mediums are much slower than memory writes, which is the cause of program slowdown. \$\endgroup\$ – apnorton Jun 22 '17 at 18:19
30
\$\begingroup\$
  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.

\$\endgroup\$
  • 3
    \$\begingroup\$ wow, I didnt know that just simply write \n instead of endl, will speed up sorting for 3 times... Thanks for advice :) \$\endgroup\$ – Adrian Jun 21 '17 at 14:51
  • 4
    \$\begingroup\$ While doing using namespace std; later or in an enclosing scope limits the lines over which the damage is spread, that doesn't make it ok. Did you perchance mean to recommend using std::symbol;? \$\endgroup\$ – Deduplicator Jun 21 '17 at 19:49
10
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.