title: counting sort of binary file in C, containing only uint16_t numbers
body: <p>I'm struggling with the following task: write a C program which takes two parameters: input.bin and output.bin. </p>
  
  <ul>
  <li>input.bin and output.bin are binary files</li>
  <li>input.bin can contain max 65535 uint16_t numbers</li>
  <li>file output.bin must be created by the program and must contain the numbers from input.bin sorted in ascending order</li>
  <li>your program can work with only 256 KB RAM and 2MB disk space</li>
  </ul>
  
  <p>So, I figured out that I can try to do it with counting sort. And here is what I do:</p>
  
  <pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;sys/types.h&gt;
  #include &lt;sys/stat.h&gt;
  #include &lt;err.h&gt;
  #include &lt;errno.h&gt;
  #include &lt;fcntl.h&gt;
  #include &lt;stdint.h&gt;
  #include &lt;unistd.h&gt;
  
  int main(int argc, char* argv[]) {
      if(argc != 3)
          errx(1, "Usage: %s &lt;input.bin&gt; &lt;output.bin&gt;", argv[0]);
  
      const char * in = argv[1];
      char * out = argv[2];
  
      struct stat st;
      if(stat(in, &amp;st) == -1)
          err(2, "fail to stat file %s", in);
  
      if(st.st_size % sizeof(uint16_t) != 0)
          errx(3, "file %s is corrupted", in);
  
      if(st.st_size / sizeof(uint16_t) &gt; 0xffff)
          warnx("overflow in file %s may occur", in);
  
      int fd_i = open(in, O_RDONLY);
      if(fd_i == -1)
          err(4, "error while opening file %s", in);
  
      uint16_t *counting = malloc(0xffff + 1);
  
      if(counting == NULL) 
          errx(5, "not enough memory");
  
      uint16_t buf[sizeof(uint16_t) * 1024];
  
      ssize_t rd_sz;
      while((rd_sz = read(fd_i, &amp;buf, sizeof(buf))) &gt; 0){
          for(uint32_t i = 0; i &lt; rd_sz; ++i){
              ++counting[buf[i]];
          }       
      }
  
      close(fd_i);
  
      ssize_t fd_o = open(out, O_CREAT | O_TRUNC | O_RDWR, S_IRUSR | S_IWUSR | S_IRGRP);
      if(fd_o == -1){
          const int _errno = errno;
          close(fd_i);
          free(counting);
          errno = _errno;
          err(6, "error while opening file %s", out);
      }
  
  
      size_t MAX = 0xffff + 1;
      size_t pos = 0; // position
      uint32_t i = 0;
      while(i &lt;= MAX){ // iterate over each number
          pos = 0;
          // fill the buffer
          size_t buf_sz = sizeof(uint16_t) * 1024 - 1;
          while(pos &lt; buf_sz &amp;&amp; i &lt;= MAX) {   
              if (counting[i] == 0) {
                  ++i; // move to next number
              } else {
                  buf[pos] = i;
                  ++pos;
                  --counting[i];
              }
          }
  
          // write the buffer to the file
          ssize_t wr_sz = write(fd_o, buf, pos);
          if (wr_sz != (ssize_t)pos) {
              err(7, "cannot write %ld bytes to output file", pos);
          }
      }
  
      close(fd_o);    
      free(counting);
      exit(0);
  }
  </code></pre>
  
  <p>But unfortunately it gives me segmentation fault, and it doesn't work and i cannot figure out why :(</p>