/media/sda-magnetic/david/Dokumente-15/fernuni-hagen/cs-i-ii/old-cs-2-03/sort-and-algorithms/sortingbymerging/themerge3.c

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

#define N 32

int merge(int startdes, int startsrc1, int startsrc2, int enddes, int endsrc1, int endsrc2, int a[N]) {
    int b[N];
    int c[N];
    int i;
    int j;
    
    int n1, n2;
    
    int k, l;
    
    n1 = endsrc1 - startsrc1;
    n2 = endsrc2 - startsrc2;
    
    for (i = startsrc1, j = 0;  i <= endsrc1;  i++, j++) 
        b[j] = a[i];
    for (i = startsrc2, j = 0;  i <= endsrc2;  i++, j++)  
        c[j] = a[i];
    
    for(i = startdes, l = 0, k = 0;  i <= enddes;  i++) {
        if((l <= n1) && (k > n2)) {
            a[i] = b[l];
            l++;
        }
        else if((l > n1) && (k <= n2)) {
            a[i] = c[k];
            k++;
        }
        else if(b[l] <= c[k]) {
            a[i] = b[l];
            l++;
        }
        else if(b[l] > c[k]) {
            a[i] = c[k];
            k++;
        }
    }    
}

int main(void) {
    int i;
    int diff;
    int j;
    
    int a[] = {1, 2, 3, 4, 1, 2, 3, 4};
    int b[32];

    for(diff = 1; diff <  8;  diff *=2) 
        for(i = 0;  (i+diff) < 8;  i+=(2*diff)) 
            merge(i, i, i+diff, i+diff*2-1, i+diff-1, i+diff*2-1, a);
            
    for(i = 0; i < 8;  i++)
        printf("%i\n", a[i]);

    srand(5);
    for (i = 0;  i < 32;  i++)
        b[i] = rand() % 64;
    
    for(diff = 1; diff <  32;  diff *=2) 
        for(i = 0;  (i+diff) < 32;  i+=(2*diff)) 
            merge(i, i, i+diff, i+diff*2-1, i+diff-1, i+diff*2-1, b);

    for (i= 0;  i < 32;  i++)
        printf("%i ", b[i]);
return 0;
}