title: How to implement merge sort from "The Introduction to Algorithms" by Cormen and Co
body: <p>I'm learning algorithms from Cormen and Co. and I have problem with implementation of merge sort from their pseudocode. I compiled it by:</p>
  
  <pre><code>$ gcc -Wall -g merge_sort.c
  </code></pre>
  
  <p>I have a problem because for numbers:</p>
  
  <pre><code>2 4 5 7 1 2 3 6
  </code></pre>
  
  <p>The result is:</p>
  
  <pre><code>1 2 2 3 3 4 5 5 
  </code></pre>
  
  <p>I tried to read carefully the pseudo code but this does not help me.
  I want to know what I'm doing wrong. Below is my code:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  #define SIZE 8
  
  void merge(int *array_of_integers, int p, int q, int r) {
      int n1 = q - p + 1;
      int n2 = r - q; 
      int i, j, k;
      int left_array[n1 + 1];
      int right_array[n2 + 1];
  
      for (i = 0; i &lt; n1; i++)
          left_array[i] = array_of_integers[p + i];
      for (j = 0; j &lt; n2; j++)
          right_array[j] = array_of_integers[q + j];
  
      i = 0;
      j = 0;
  
      for (k = p; k &lt; r; k++){
          if (left_array[i] &lt;= right_array[j]) {
              array_of_integers[k] = left_array[i];
              i++;
          } else {
              array_of_integers[k] = right_array[j];
              j++;
          }   
      }
  }
  
  void merge_sort(int *array_of_integers, int p, int r) {
      if (p &lt; r) {
          int q = (p + r) / 2;
          merge_sort(array_of_integers, p, q);
          merge_sort(array_of_integers, q + 1, r);
          merge(array_of_integers, p, q, r);
      }
  }
  
  void print_array(int *array_of_integers, int amout_of_integers) {
      int i;
      for(i = 0; i &lt; amout_of_integers; i++)
          printf("%d ", array_of_integers[i]);
      puts("");
  }
  
  int main(void) {
      int dataset[] = { 2, 4, 5, 7, 1, 2, 3, 6 };
  
      print_array(dataset, SIZE);
      merge_sort(dataset, 0, SIZE);
      print_array(dataset, SIZE);
  
      return 0;
  }
  </code></pre>
  
  <p>Edit: (Correct solution)</p>
  
  <pre><code> void merge(int *array_of_integers, int p, int q, int r) {
       int n1 = q - p + 1;
       int n2 = r - q; 
       int i, j, k;
       int left_array[n1 + 1];
       int right_array[n2 + 1];
  
       left_array[n1] = 123456798;
       right_array[n2] = 123456798;
  
       for (i = 0; i &lt; n1; i++)
           left_array[i] = array_of_integers[p + i];
       for (j = 0; j &lt; n2; j++)
           right_array[j] = array_of_integers[q + j + 1];
  
       i = 0;
       j = 0;
  
       for (k = p; k &lt;= r; k++) {
           if (left_array[i] &lt;= right_array[j]) {
               array_of_integers[k] = left_array[i];
               i++;
           } else {
               array_of_integers[k] = right_array[j];
               j++;
           }
       }
   }
  
   void merge_sort(int *array_of_integers, int p, int r) {
       if(p &lt; r) {
           int q = (p + r) / 2;
           merge_sort(array_of_integers, p, q);
           merge_sort(array_of_integers, q + 1, r);
           merge(array_of_integers, p, q, r);
       }
   }
  </code></pre>