Merging multiple sorted arrays in C

Question

Trying to merge 8 pre-sorted arrays. I'm fairly new to C, but this is what I've come up with so far. Needless to say it doesn't work. What I can't figure out is why. I've based it off the C++ mergesort implementation here and tried to extend it to 8 dimensions and simplify it a bit, but for some reason it tends to give me the elements of the first array, followed by 34, 30 then it repeats 23 until the end. It doesn't even pick up that 21 is the smallest value on the first iteration.

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 output[40];
int t1, t2, t3, t4, t5, t6, t7, t8;
t1 = 0;
t2 = 0;
t3 = 0;
t4 = 0;
t5 = 0;
t6 = 0;
t7 = 0;
t8 = 0;
int p = 0;
int temp1;
int temp2;

while(p < 40) {
    if (t1 < 5) {
        temp1 = 1;
        temp2 = test1[t1];
    }else if (test2[t2] <= test1[t1] && t2 < 5) {
        temp1 = 2;
        temp2 = test2[t2];
    }else if (test3[t3] <= temp2 && t3 < 5) {
        temp1 = 3;
        temp2 = test3[t3];
    }else if (test4[t4] <= temp2 && t4 < 5) {
        temp1 = 4;
        temp2 = test4[t4];
    }else if (test5[t5] <= temp2 && t5 < 5) {
        temp1 = 5;
        temp2 = test5[t5];
    }else if (test6[t6] <= temp2 && t6 < 5) {
        temp1 = 6;
        temp2 = test6[t6];
    }else if (test7[t7] <= temp2 && t7 < 5) {
        temp1 = 7;
        temp2 = test7[t7];
    }else if (test8[t8] <= temp2 && t8 < 5) {
        temp1 = 8;
        temp2 = test8[t8];
    }
    switch(temp1) {
        case 1:
            output[p] = temp2;
            t1++;
            break;
        case 2:
            output[p] = temp2;
            t2++;
            break;
        case 3:
            output[p] = temp2;
            t3++;
            break;
        case 4:
            output[p] = temp2;
            t4++;
            break;
        case 5:
            output[p] = temp2;
            t5++;
            break;
        case 6:
            output[p] = temp2;
            t6++;
            break;
        case 7:
            output[p] = temp2;
            t7++;
            break;
        case 8:
            output[p] = temp2;
            t8++;
            break;
    }
    printf("%d\n",  output[p]);
    p++;
}

Thanks for any help you can offer.

Answer 1

This is why you get the first 5 elements of the first array:

if (t1 < 5) {
        temp1 = 1;
        temp2 = test1[t1];

Your code is specifically ensuring the first 5 elements of the first array get selected first. You should be comparing the value of the next element in test1 against the next element in the other arrays, not just blindly picking it. Also, your use of if..then..else if.. else if... is not correct. If you find out that array 2's next element is less than array 1's next element, you still have to examine whether arrays 3, 4 and 5 are less.

Try structuring your code like this

int temp1 = -1;
if (t1 < 5) {
    temp1=1;
    temp2=test1[t1];
}
if ((t2 < 5) && ((temp1 < 0) || (test2[t2] < temp2))) {
    temp1=2;
    temp2=test2[t2];
}
if (t3...

followed by your existing switch statement.

Answer 2

hatchet already told you what went wrong, if ... else if ... will execute the second block if and only if the second condition is valid and the first one wasn't valid.

However, I believe your switch() and if-else based program is a little bit hard to extend, since you need to change all the fixed fields and values to sort another set of arrays. The following program/function provides the same as yours, but is easier to extend. It uses an additional array cursor to save the current position (similar to your t1,t2,...) (Ideone Demo).

#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;
}

Answer 3

What I've done in the (distant) past is to sort the first element of each list with a tag sort, select the first one in the sorted list to add to the merged list, then replace the moved item with the next one from its list (which is why you need a tag sort of some flavor, to identify where the replacement should come from) and re-sort. The sorting of the head elements can be with a bubble sort, since after the initial sort you only need one pass to properly re-order things following removal/replacement.