Сортировка слиянием работает некорректно - C (СИ)

Формулировка задачи:

Здравствуйте! Читаю Алгоритмы. Построение и анализ. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Попытался реализовать на си, но не верно. Помогите, пожалуйста!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define COUNT 9
 
void merge(int *arr, int p, int q, int r)
{
    int i,j,k;
    int n1 = q - p;
    int n2 = r - q;
 
    int *larr = malloc(sizeof(int)*(n1+1));
    int *rarr = malloc(sizeof(int)*(n2+1));
    
    for( i = 0; i < n1; i++ ) 
        larr[i] = arr[p+i];
    for( j = 0; j < n2; j++ )  
        rarr[j] = arr[q+j];
    
    larr[n1] = 999999;
    rarr[n2] = 999999;
    i = 0;
    j = 0;
    
    for( k = p; k < r; k++ ) {
        if( larr[i] <= rarr[j] && i < n1 )
            arr[k] = larr[i++];
        else
            arr[k] = rarr[j++];
    }
    free(larr);
    free(rarr);
}
 
void merge_sort( int *arr, int p, int r )
{
    if( p < r ) {
        int q = (p+r)/2;
        merge_sort( arr, p, q );
        merge_sort( arr, q+1, r);
        merge(arr,p,q,r);
    }
}
 
int main( int argc, char ** argv )
{
    int i,j;
    int array[COUNT];
 
    // заполнение случайными числами
    srand(time(NULL));
 
    for( i = 0; i < COUNT; i++ ) 
        array[i] = rand()%255;
        
    // вывод массива перед сортировкой
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);
    
    // сортировка
    merge_sort( array, 0, COUNT );
    
    // вывод массива после сортировки
    printf("%c",'\n');
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);    
    
    return EXIT_SUCCESS;
}

Решение задачи: «Сортировка слиянием работает некорректно»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
 
#define COUNT 9
 
void merge(int *arr, int p, int q, int r)
{
    int i,j,k;
    int n1 = q - p;
    int n2 = r - q;
    int *larr,*rarr;
 
    if(n1==0 || n2==0)
        return;
 
    larr = (int*)malloc(sizeof(int)*n1);
    rarr = (int*)malloc(sizeof(int)*n2);
 
    for( i = 0; i < n1; i++ ) 
        larr[i] = arr[p+i];
    for( j = 0; j < n2; j++ ) 
        rarr[j] = arr[q+j];
 
    i = 0;
    j = 0;
 
    for( k = p; k < r; k++ ) {
        if(j==n2 || ( i < n1 && larr[i] <= rarr[j]) )
            arr[k] = larr[i++];
        else
            arr[k] = rarr[j++];
    }
    free(larr);
    free(rarr);
}
 
void merge_sort( int *arr, int p, int r )
{
    int q;
    if( r-p > 1 ) {
        q = (p+r)/2;
        merge_sort( arr, p, q );
        merge_sort( arr, q, r);
        merge(arr,p,q,r);
    }
}
 
int main( int argc, char ** argv )
{
    int i;
    int array[COUNT];
 
    // заполнение случайными числами
    srand((unsigned)time(NULL));
 
    for( i = 0; i < COUNT; i++ ) 
        array[i] = rand()%255;
 
    // вывод массива перед сортировкой
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);
 
    // сортировка
    merge_sort( array, 0, COUNT );
 
    // вывод массива после сортировки
    printf("\n");
    for( i = 0; i < COUNT; i++ )
        printf("%d ", array[i]);    
        return EXIT_SUCCESS;
}

Объяснение кода листинга программы

Включаем необходимые заголовочные файлы
Объявляем функцию merge, которая будет выполнять слияние массивов
В функции merge определяем переменные i, j, k для работы с индексами массива
Определяем переменные n1 и n2 для хранения размеров сортируемых массивов
Выделяем память под массивы larr и rarr с помощью функции malloc
Копируем элементы из исходного массива в larr и rarr
Создаем временный массив arr для хранения отсортированных значений
Сортируем элементы массива с помощью цикла for и условного оператора if
Освобождаем память, выделенную под larr и rarr
Объявляем функцию merge_sort, которая будет выполнять сортировку массива слиянием
В функции merge_sort определяем переменную q для хранения индекса серединного элемента
Проверяем условие для рекурсивного вызова функции merge_sort
Рекурсивно вызываем функцию merge_sort для левой и правой половин массива
Рекурсивно вызываем функцию merge_sort для правой и левой половин массива
Вызываем функцию merge для слияния отсортированных половин массива
В функции main создаем массив array типа int с длиной 9
Заполняем массив случайными числами с помощью функции rand и srand
Выводим массив на экран с помощью цикла for и функции printf
Вызываем функцию merge_sort для сортировки массива array
Выводим отсортированный массив на экран с помощью цикла for и функции printf
Возвращаем успешный результат выполнения программы с помощью return EXIT_SUCCESS