mergeSort

/*
 * File:   main.c
 * Author: Gerardo Cicalese
 *
 * Created on 18 novembre 2019, 14.22
 */

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

void merge(int *, int, int *, int, int *);
void mergeSort(int *, int, int *);

int main(void)
{
    srand(time(NULL));
    int array[10], temp[10];

    for(int i=0; i<10; ++i)
        array[i] = rand()%100;

    mergeSort(array, 10, temp);

    for(int i=0; i<10; ++i)
        printf("%d\t", array[i]);

    return 0;
}

void merge(int * a, int na, int * b, int nb, int * c)
{
    while(na > 0 && nb > 0)
        if(*a < *b)
        {
            *(c++) = *(a++);
            --na;
        }
        else
        {
            *(c++) = *(b++);
            --nb;
        }

    while(na > 0)
    {
        *(c++) = *(a++);
        --na;
    }

    while(nb > 0)
    {
        *(c++) = *(b++);
        --nb;
    }
}

void mergeSort(int * array, int len, int * temp)
{
    if(len <= 1)
        return;

    int m = len/2;

    mergeSort(array, m, temp);
    mergeSort(array+m, len-m, temp);

    merge(array, m, array+m, len-m, temp);

    for(int i=0; i<len; ++i)
        array[i] = temp[i];
}