#include <stdio.h>
#include <stdlib.h>
#include <string.h> 

char str[] = "%u %u %u %u %u %u %u %u %u %u \n";

struct dividearrays
{
    unsigned int * begin;
    unsigned int * middle;
    unsigned int * end;
};

// Функция принимает в качестве аргументов:
//// Указатель на начало массива, указатель на точку разделения,
//// указатель на конец массива
// Функция сортирует массив, если части массива, разделенные точкой
// разделения, сами отсортированы

void mergesort
          (
            unsigned int * array,
            unsigned int * split,
            unsigned int * end
          )

{
    unsigned int *result = malloc((end-array)*sizeof(unsigned int));
    unsigned int *result_ptr = result;
    unsigned int *arr1, *arr2;
    arr1 = array;
    arr2 = split;
    //printf(str, array[0], array[1], array[2], array[3], array[4],
    //            array[5], array[6], array[7], array[8], array[9]); 

    while ( (arr1 != split) && (arr2 != end) )
    {
        if ( *arr1 > *arr2 )
        {
            *result_ptr = *arr2;
            arr2++;
        } else
        {
            *result_ptr = *arr1;
            arr1++;
        }
    result_ptr++;
    }
    if (arr1  == split)
    { //   назначение - result, источник - arr2, размер копирования - ...
        memcpy(result_ptr, arr2, (end-arr2) * sizeof(unsigned int) );
    } else
    {
        memcpy(result_ptr, arr1, (split-arr1)*sizeof(unsigned int) );
    }    
    
    memcpy (array, result, (end-array)*sizeof(unsigned int) );
    free (result);
}

// Функция принимает в качестве аргументов начало и конецмассива
// возвращает указатель на середину массива

unsigned int * findmiddle
          (
            unsigned int * array,
            unsigned int * end
          )
{
    unsigned int * middle = array + ( (end - array) / 2 );
    
    if ( middle == array )
    {
        return NULL;
    }
    return middle;
    
}




int main(void)
{
/////////////


/////////////
    

unsigned int arr[] = { 3, 243, 1, 26, 1111, 16, 78, 17, 1, 66, 13333, 34646, 24, 234, 1832,
                       13355, 234, 2761, 1, 666, 1337, 1488, 66666, 555, 1365, 136, 192, 256, 6566,
                       13513, 1356,666666, 999  };


unsigned int *middle;
size_t end = sizeof(arr)/sizeof(arr[0]);

// массив, в котором будут
// Начало, конец, середина.

struct dividearrays arr_div[33];
struct dividearrays *arr_div_p1, *arr_div_p2;
 
 

size_t i;


middle = findmiddle(arr, &arr[end]);

arr_div[0].begin  = arr;
arr_div[0].middle = findmiddle(arr, &arr[end]);
arr_div[0].end    = &arr[end];

arr_div_p1 = &arr_div[0];
arr_div_p2 = &arr_div[1];

///////////////////////
    while ( arr_div_p1 != arr_div_p2 )
    {
        
        // Если в результате деления первой половины массива на две
        // мы не пытались делить массив размером 1
        if ( findmiddle((*arr_div_p1).begin,  (*arr_div_p1).middle) != NULL )
        {
            // То тогда начало массива совпадает с началом того, который мы делим
            arr_div_p2->begin  = arr_div_p1->begin;

            // Конец это серединка того массива, который мы делим
            arr_div_p2->end    = findmiddle(arr_div_p1->begin,  arr_div_p1->end);

            // А его серединка это серединка между началом массива (этого) и концом массива (этого)
            arr_div_p2->middle = findmiddle(arr_div_p2->begin, arr_div_p2->end);

            // Мы эту инфу записали в массив структур, и нам надо тогда записывать следующий в следующее
            // Иначе бы мы повторно перезаписывали в то же место
            arr_div_p2++;
        }


        // Если в результате деления второй половины массива на две
        // мы не пытались делить массив размером 1        
        if ( findmiddle((*arr_div_p1).middle, (*arr_div_p1).end   ) != NULL )
        {
            // Начало это серединка того массива, который мы делим
            arr_div_p2->begin  = findmiddle(arr_div_p1->begin, arr_div_p1->end);

            // То тогда конец массива совпадает с концом того, который мы делим
            arr_div_p2->end    = arr_div_p1->end;

            // А его серединка это серединка между началом массива (этого) и концом массива (этого)
            arr_div_p2->middle = findmiddle(arr_div_p2->begin, arr_div_p2->end);

            // Мы эту инфу записали в массив структур, и нам надо тогда записывать следующий в следующее
            // Иначе бы мы повторно перезаписывали в то же место
            arr_div_p2++;
        }

        // Переходим к следующей штуке, в которой есть начало середина конец
        // Если ..., выйдем из этого цикла
        arr_div_p1++;
    }
///////////////////////


while ( arr_div_p2 != &arr_div[0])
{
    arr_div_p2--; // <--- Теперь указатель стоит на одну ступеньку раньше, и он указывает на штуковину
    mergesort(
            arr_div_p2->begin,
            arr_div_p2->middle,
            arr_div_p2->end
          );
}


for (i = 0; i < 33; i++)
{
  printf("%u ", arr[i]);
}
  printf("\n");
///////////////////////

return 0;
}