title: Implementing external mergesort. How to get started?
body: <p>For a project I have to implement an external mergesort algorithm. It will be used to sort a file with mostly numbers or strings and will be some GBs in size. This is the definition of the mergesort that I've been given </p>
  
  <pre><code>void MergeSort (char *infile,
                  unsigned char field,
                  block_t *buffer,
                  unsigned int nmem_blocks,
                  char *outfile,
                  unsigned int *nsorted_segs,
                  unsigned int *npasses,
                  unsigned int *nios);
  </code></pre>
  
  <p>I'm not allowed to change that. The first argument is the file that I'm going to sort. The second the field according to which I want to sort the file (doesn't interest me right now), the third argument is the buffer. Which is a struct. Here is the definition of a block </p>
  
  <pre><code>typedef struct
  {
      unsigned int blockid;
      unsigned int nreserved; // how many reserved entries
      record_t entries[MAX_RECORDS_PER_BLOCK]; // array of records
      bool valid;  // if set, then this block is valid
      unsigned char misc;
      unsigned int next_blockid;
      unsigned int dummy;
  
  } block_t;
  </code></pre>
  
  <p>the fourth argument is the number of blocks in memory. The last three arguments can be set by me.</p>
  
  <p>My questions are: </p>
  
  <ol>
  <li><p>Do I take the file and cut it into two files? </p></li>
  <li><p>Is the buffer a file stored in the harddrive or does it stay in the memory? Do I have to create a new file? I'm a little confused with this part.</p></li>
  </ol>
  
  <p>These are my thoughts to start right now. First I get the file and split it in two parts. I also create a buffer, which I don't know what size it should have. Then I read the first block of records from the first file, and compare the numbers to the first block of records of the second file. Whenever the number is lesser or equal to another I will send it to the output file. Can you evaluate my stream of thoughts? Or am I thinking it wrong?</p>