// main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "merge_sort.h"
int read_array(const char *name, double *array, int n);
void rand_array(double *array, int n);
void print_array(double *array, int n);
int f_up(double a, double b);
int f_down(double a, double b);

int f_up(double a, double b)
{
    if( a>b )
        return 1;

    if( a<b )
        return -1;

    return 0;
}

int f_down(double a, double b)
{
    if( a>b )
        return -1;

    if( a<b )
        return 1;

    return 0;
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов.
 * Ф-ия возвращает:
 * -2, если не удалось прочитать элемент;
 * -1, если не удалось открыть файл;
 * 0, в случае успешного завершения.
 * */
int read_array(const char *name, double *array, int n)
{
    FILE *input;
    int i;

    if( !(input = fopen(name, "r")) )
        return -1;

    for( i = 0; i<n; i++ )
    {
        if( fscanf(input, "%lf", array + i)!=1 )
        {
            fclose(input);
            return -2;
        }
    }

    fclose(input);
    return 0;
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов. */
void rand_array(double *array, int n)
{
    int i;

    for( i = 0; i<n; i++ )
        array[i] = rand();
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов.
 * */
void print_array(double *array, int n)
{
    int i;

    if( n>20 )
        n = 20;

    for( i = 0; i<n; i++ )
        printf("Array[%d]=%lf\n", i, array[i]);
}

int main(int argc, const char *argv[])
{
    int n, result_read;
    double *a, *b;
    clock_t time_begin;

    if( ((argc!=2) && (argc!=3)) || (sscanf(argv[1], "%d", &n)!=1) || (n<=0) )
    {
        fprintf(stderr, "Usage: %s size_of_array [file_with_array]\t\t([size_of_array]>0)\t(array is random if no file_with_array)\n", argv[0]);
        return 1;
    }

    if( !(a = (double *)malloc(n*sizeof(double))) )
    {
        fprintf(stderr, "Can not allocate memory!\n");
        return 2;
    }
    if( !(b = (double *)malloc(n*sizeof(double))) )
    {
        fprintf(stderr, "Can not allocate memory!\n");
        free(a);
        return 2;
    }
    // Память выделена

    if( argc==3 )
    {
        result_read = read_array(argv[2], a, n);
        if( result_read<0 )
        {
            switch( result_read )
            {
            case -2:
                fprintf(stderr, "Can not read element from %s\n", argv[2]);
                break;
            case -1:
                fprintf(stderr, "Can not open file %s\n", argv[2]);
                break;
            default:
                fprintf(stderr, "Unknown error %d in file %s\n", result_read, argv[2]);
            }

            free(a);
            free(b);
            return 3;
        }
    } else
    {
        rand_array(a, n);
    }
    // Массив считан или сгенерирован случайный

    printf("Array a[]:\n");
    print_array(a, n);

    time_begin = clock();
    merge_sort(a, b, n, &f_up);
    printf("Time: %.2f seconds\nArray b[]:\n", (float)( clock() - time_begin )/CLOCKS_PER_SEC);
    print_array(b, n);

    free(a);
    free(b);
    return 0;
}



// merge_sort.h
#ifndef MERGE_SORT_H
#define MERGE_SORT_H

void merge_sort(double *a, double *b, int n, int (*p)(double, double));

#endif



// merge_sort.c
#include "merge_sort.h"
void merge(double *a, double *b, double *c, int n, int m, int (*p)(double, double));

/* Предполагается, что n>0, и по указателю a расположен массив из n элементов.
 * Сортировка Неймана.
 * */
void merge_sort(double *a, double *b, int n, int (*p)(double, double))
{
    int i, size, num;

    for( size = 1; size<=(int)(n/2); size *= 2 )// Размер группы
    {
        for( num = 0; num<=(int)(n/size) - 2; num += 2 )// Номер группы
        {
            merge(a + num*size, a + (num + 1)*size, b, size, size, p);
            for( i = 0; i<2*size; i++ )
            {
                a[i + num*size] = b[i];
            }
        }
    }

    merge(a, a + size, b, size, n - size, p);
}

/* Предполагается, что n>0, m>0 и по указателю a записан неубывающий массив длины n, по указателю b неубывающий массив из m элементов,
 * по указателю c выделена память для (n + m) элементов.
 * Ф-ия строит неубывающий массив слиянием a и b.
 * */
void merge(double *a, double *b, double *c, int n, int m, int (*p)(double, double))
{
    int i = 0, j = 0, k;

    for( k = 0; (i<n) && (j<m); k++ )
    {
        if( p(b[j], a[i])>0 )
        {
            c[k] = a[i];
            i++;
        } else
        {
            c[k] = b[j];
            j++;
        }
    }

    for( ; i<n; k++, i++ )
        c[k] = a[i];

    for( ; j<m; k++, j++)
        c[k] = b[j];
}