#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]++;
}
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){
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPGxpbWl0cy5oPgoKaW50IG11bHRpbWVyZ2UoCiAgICBpbnQgKiBjb25zdCAqIGNvbnN0IGFycmF5cywgICAgICAvLyBhcnJheXMgaG9sZGluZyB0aGUgZGF0YQogICAgaW50IGNvbnN0ICogY29uc3QgYXJyYXlzaXplcywgICAgLy8gc2l6ZXMgb2YgdGhlIGFycmF5cyBpbiBgYXJyYXlzYAogICAgaW50IG51bWJlcl9vZl9hcnJheXMsICAgICAgICAgICAgLy8gbnVtYmVyIG9mIGFycmF5cwogICAgaW50ICogY29uc3Qgb3V0cHV0ICAgICAgICAgICAgICAgLy8gcG9pbnRlciB0byBvdXRwdXQgYnVmZmVyCil7CiAgICBpbnQgaSA9IDA7ICAgICAgIC8vIG91dHB1dCBjdXJzb3IKICAgIGludCBqID0gMDsgICAgICAgLy8gaW5kZXggZm9yIG1pbmltdW0gc2VhcmNoCiAgICBpbnQgbWluOyAgICAgICAgIC8vIG1pbmltdW0gaW4gdGhpcyBpdGVyYXRpb24KICAgIGludCBtaW5wb3NpdGlvbjsgLy8gcG9zaXRpb24gb2YgdGhlIG1pbmltdW0KCiAgICAvLyBjdXJzb3IgZm9yIHRoZSBhcnJheXMKICAgIGludCAqIGN1cnNvciA9IGNhbGxvYyhudW1iZXJfb2ZfYXJyYXlzLHNpemVvZihpbnQpKTsKCiAgICBpZihjdXJzb3IgPT0gTlVMTCkKICAgICAgICByZXR1cm4gLTE7CgogICAgd2hpbGUoMSl7CiAgICAgICAgbWluID0gSU5UX01BWDsKICAgICAgICBtaW5wb3NpdGlvbiA9IC0xOyAvLyBpbnZhbGlkIHBvc2l0aW9uCgogICAgICAgIC8vIEdvIHRocm91Z2ggdGhlIGN1cnJlbnQgcG9zaXRpb25zIGFuZCBnZXQgdGhlIG1pbmltdW0KICAgICAgICBmb3IoaiA9IDA7IGogPCBudW1iZXJfb2ZfYXJyYXlzOyArK2opewoKICAgICAgICAgICAgaWYoY3Vyc29yW2pdIDwgYXJyYXlzaXplc1tqXSAmJiAgLy8gZW5zdXJlIHRoYXQgdGhlIGN1cnNvciBpcyBzdGlsbCB2YWxpZAogICAgICAgICAgICAgICBhcnJheXNbal1bY3Vyc29yW2pdXSA8IG1pbil7ICAvLyB0aGUgZWxlbWVudCBpcyBzbWFsbGVyCiAgICAgICAgICAgICAgICBtaW4gPSBhcnJheXNbal1bY3Vyc29yW2pdXTsgIC8vIHNhdmUgdGhlIG1pbmltdW0gLi4uCiAgICAgICAgICAgICAgICBtaW5wb3NpdGlvbiA9IGo7ICAgICAgICAgICAgIC8vIC4uLiBhbmQgaXRzIHBvc2l0aW9uCiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIC8vIGlmIHRoZXJlIGlzIG5vIG1pbmltdW0sIHRoZW4gdGhlIHBvc2l0aW9uIHdpbGwgYmUgaW52YWxpZAoKICAgICAgICBpZihtaW5wb3NpdGlvbiA9PSAtMSkKICAgICAgICAgICAgYnJlYWs7CgogICAgICAgIC8vIHVwZGF0ZSB0aGUgb3V0cHV0IGFuZCB0aGUgc3BlY2lmaWMgY3Vyc29yICAgICAgICAgICAgCiAgICAgICAgb3V0cHV0W2krK10gPSBtaW47CiAgICAgICAgY3Vyc29yW21pbnBvc2l0aW9uXSsrOwogICAgfQogICAgZnJlZShjdXJzb3IpOwoKICAgIHJldHVybiAwOwp9CgppbnQgbWFpbigpCnsKICAgIGludCBpID0gMDsKICAgIGludCB0ZXN0MVs1XSA9IHsyMywgMjQsIDI1LCAzMywgNTF9OwogICAgaW50IHRlc3QyWzVdID0gezIxLCAzNCwgNDQsIDUwLCA2Mn07CiAgICBpbnQgdGVzdDNbNV0gPSB7MzQsIDM2LCA0MSwgNDQsIDQ2fTsKICAgIGludCB0ZXN0NFs1XSA9IHszMCwgMzEsIDMyLCAzNSwgNDB9OwogICAgaW50IHRlc3Q1WzVdID0gezU0LCA1NiwgNTcsIDU4LCA2MH07CiAgICBpbnQgdGVzdDZbNV0gPSB7MzEsIDMzLCAzNiwgNTEsIDUyfTsKICAgIGludCB0ZXN0N1s1XSA9IHs0NCwgNDYsIDc2LCA3OCwgNzl9OwogICAgaW50IHRlc3Q4WzVdID0gezIzLCAzMywgNDMsIDU0LCA2M307CgogICAgaW50ICp0ZXN0W10gPSB7dGVzdDEsIHRlc3QyLCB0ZXN0MywgdGVzdDQsIHRlc3Q1LCB0ZXN0NiwgdGVzdDcsIHRlc3Q4fTsKICAgIGludCB0ZXN0c2l6ZXNbXSA9IHs1LDUsNSw1LDUsNSw1LDV9OwoKICAgIGludCBvdXRwdXRbNDBdOwoKICAgIG11bHRpbWVyZ2UodGVzdCx0ZXN0c2l6ZXMsOCxvdXRwdXQpOwoKICAgIHdoaWxlKGkgPCAzMCl7CiAgICAgICAgcHJpbnRmKCIlaVxuIixvdXRwdXRbaSsrXSk7CiAgICB9ICAgIAoKICAgIHJldHVybiAwOwp9Cg==