如何从Cormen和Co的“算法介绍”中实现合并排序

$gcc -Wall -g merge_sort.c

我有一个问题,因为数字：

2 4 5 7 1 2 3 6

结果是：

1 2 2 3 3 4 5 5

我试图仔细阅读伪代码,但这并不能帮助我.
我想知道我在做错什么以下是我的代码：

#include <stdio.h>

#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 < n1; i++)
    left_array[i] = array_of_integers[p + i];
  for(j = 0; j < n2; j++)
    right_array[j] = array_of_integers[q + j];

  i = 0;
  j = 0;

  for(k = p; k < r; k++){
    if(left_array[i] <= 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 r){
  if(p < 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,q,r);
  }
}


void print_array(int * array_of_integers,int amout_of_integers){
  int i;
  for(i = 0; i < 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,SIZE);
  print_array(dataset,SIZE);

  return 0;
}

编辑：(正确解决方案)

void merge(int * array_of_integers,int r){
   int n1 = q - p + 1;
   int n2 = r - q; 
   int i,k;
   int left_array[n1+1];
   int right_array[n2+1];

   left_array[n1] = 123456798;
   right_array[n2] = 123456798;

   for(i = 0; i < n1; i++)
     left_array[i] = array_of_integers[p + i];
   for(j = 0; j < n2; j++)
     right_array[j] = array_of_integers[q + j + 1];

   i = 0;
   j = 0;

   for(k = p; k <= r; k++){
     if(left_array[i] <= 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 r){
   if(p < r){
     int q = (p+r)/2;
     merge_sort(array_of_integers,q);
     merge_sort(array_of_integers,r);
     merge(array_of_integers,r);
   }
 }