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

int multimerge(
    int * const * const arrays,      // arrays holding the data
    int const * const arraysizes,    // sizes of the arrays in `arrays`
    int number_of_arrays,            // number of arrays
    int * const output               // pointer to output buffer
){
    int i = 0;       // output cursor
    int j = 0;       // index for minimum search
    int min;         // minimum in this iteration
    int minposition; // position of the minimum

    // cursor for the arrays
    int * cursor = calloc(number_of_arrays,sizeof(int));

    if(cursor == NULL)
        return -1;

    while(1){
        min = INT_MAX;
        minposition = -1; // invalid position

        // Go through the current positions and get the minimum
        for(j = 0; j < number_of_arrays; ++j){

            if(cursor[j] < arraysizes[j] &&  // ensure that the cursor is still valid
               arrays[j][cursor[j]] < min){  // the element is smaller
                min = arrays[j][cursor[j]];  // save the minimum ...
                minposition = j;             // ... and its position
            }
        }

        // if there is no minimum, then the position will be invalid

        if(minposition == -1)
            break;

        // update the output and the specific cursor            
        output[i++] = min;
        cursor[minposition]++;
    }
    free(cursor);

    return 0;
}

int main()
{
    int i = 0;
    int test1[5] = {23, 24, 25, 33, 51};
    int test2[5] = {21, 34, 44, 50, 62};
    int test3[5] = {34, 36, 41, 44, 46};
    int test4[5] = {30, 31, 32, 35, 40};
    int test5[5] = {54, 56, 57, 58, 60};
    int test6[5] = {31, 33, 36, 51, 52};
    int test7[5] = {44, 46, 76, 78, 79};
    int test8[5] = {23, 33, 43, 54, 63};

    int *test[] = {test1, test2, test3, test4, test5, test6, test7, test8};
    int testsizes[] = {5,5,5,5,5,5,5,5};

    int output[40];

    multimerge(test,testsizes,8,output);

    while(i < 30){
        printf("%i\n",output[i++]);
    }    

    return 0;
}