Merging and sorting two sorted arrays containing doubles in C

Question

So I have two arrays consisting of double numbers, they are sorted.

I would like to most efficiently combine these into one array and have this one array also sorted.

My first thought was that maybe you could simply join them together then use qsort on it, but this wouldn't be that efficient. So maybe instead using merge sort? However, I am kind of lost on how to implement merge sort in C, any ideas?

I am using the code from one of the answers to try merge sorting. I have not made it into its own method just yet, will do that after I have gotten it to work.

double partitions[][5] = {{45.0, 5.0, 88.4, 0.4, 44.0}, {1000.0, 2.0, 3.4, 7.0, 50.0}};
double* res;

int n1 = sizeof(partitions[0])/sizeof(partitions[0][0]);
int n2 = sizeof(partitions[1])/sizeof(partitions[1][0]);
int n3 = n1 + n2;

res = malloc(n3 * sizeof(double));

// Merging starts
int i = 0;
int j = 0;
int k = 0;

while (i < n1 && j < n2) {
    if (partitions[0][i] - partitions[1][j] < 0.000001) {
        res[k] = partitions[0][i];
        i++;
        k++;
    }
    else {
        res[k] = partitions[1][j];
        k++;
        j++;
    }
}

/* Some elements in array 'arr1' are still remaining
where as the array 'arr2' is exhausted */
while (i < n1) {
    res[k] = partitions[0][i];
    i++;
    k++;
}

/* Some elements in array 'arr2' are still remaining
where as the array 'arr1' is exhausted */
while (j < n2) {
    res[k] = partitions[1][j];
    k++;
    j++;
}

int m;
for (m = 0; m < n3; m++)
    printf("%f \n", res[m]);

so, you don't want a sorting algorithm, you just want a merging algorithm. Let's be clear on that. — Marcus Müller, Sep 09 '17 at 09:33
@VladfromMoscow that's not a solution. It's not a solution in the sense that it doesn't help OP's C code. — Marcus Müller, Sep 09 '17 at 09:34
https://stackoverflow.com/questions/2348374/merging-two-sorted-linked-lists — melpomene, Sep 09 '17 at 09:36
Possible duplicate of [Non-Recursive Merge Sort](https://stackoverflow.com/questions/1557894/non-recursive-merge-sort) — akshayk07, Sep 09 '17 at 09:37
Surely, this is kinda intuitive? Taking the largest, or equal, value from the top of the two sorted arrays and storing it in the result? Or the smallest from the bottom? — Martin James, Sep 09 '17 at 09:37
Possible duplicate of [Merging two sorted linked lists](https://stackoverflow.com/questions/2348374/merging-two-sorted-linked-lists) — gsamaras, Sep 09 '17 at 09:38

coder · Accepted Answer · 2017-09-09T10:00:54.887

2

Since the arrays are sorted you only need the merge part of the merge sort which is O(n1+n2) where n1 is the length of the one array and n2 is the length of the other array:

For example:

void merge(int n1, int n2){ //suppose global arrays arr1,arr2 and result array

      i = 0;
      j = 0;
      k = 0;

    // Merging starts
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            res[k] = arr1[i];
            i++;
            k++;
        } 
        else {
            res[k] = arr2[j];
            k++;
            j++;
        }
    }

    /* Some elements in array 'arr1' are still remaining
    where as the array 'arr2' is exhausted */

    while (i < n1) {
        res[k] = arr1[i];
        i++;
        k++;
    }

    /* Some elements in array 'arr2' are still remaining
    where as the array 'arr1' is exhausted */

    while (j < n2) {
        res[k] = arr2[j];
        k++;
        j++;
    }
}

Also I just note that your arrays contain double so you need to change the condition when comparing two numbers. For example instead of if (arr1[i] <= arr2[j]) you need to write a condition for: if (arr1[i] < arr2[j]) and then the else part.

edited Sep 09 '17 at 10:00

answered Sep 09 '17 at 09:39

coder

12,832
5
39
53

Are the initial vlaues of i,j,k = 0? – osk Sep 09 '17 at 09:43
@osk, yes edited the answer watch the part about doubles you can't compare for equality using ==. – coder Sep 09 '17 at 09:47
I have two vectors that I'm trying this on, partitions[0] and partitions[1]. I put if (partitions[0][i] - partitions[1][j] < 0.000001) just to test but I'm getting a merged array in return that is not sorted – osk Sep 09 '17 at 09:51
I will add it to the op – osk Sep 09 '17 at 09:53
You can check my op now, thank you for the help by the way! – osk Sep 09 '17 at 09:55
I don't understand the part about comparing doubles. What's wrong with `arr1[i] <= arr2[j]` and how would adding an epsilon help? – melpomene Sep 09 '17 at 09:58
Actually I think you don't need to check for equality so just try arr1[i] – coder Sep 09 '17 at 10:00
@coder Yes, you can. There's nothing wrong with `==` or `<=`. – melpomene Sep 09 '17 at 10:00
@ melpomene , what I'm missing here? how could you check if two doubles are equal? (see: https://stackoverflow.com/questions/21260776/how-to-compare-double-numbers) – coder Sep 09 '17 at 10:02
@coder "*For example, if you are sorting numbers in a list or other data structure, you should not use any tolerance for comparison.*" Did you even read the answer? – melpomene Sep 09 '17 at 10:05
I added your code to my original post @coder, I'm not sure what I'm doing wrong. – osk Sep 09 '17 at 10:11
@melpomene , ok so what you're saying is that you don't need to check for equality? – coder Sep 09 '17 at 10:16
@osk - you are stull using `partitions[0][i] - partitions[1][j] < 0.000001`, that's your problem – Les Sep 09 '17 at 10:18
@osk,as I said above replace: `partitions[0][i] - partitions[1][j] < 0.000001` with `partitions[0][i] < partitions[1][j] ` (if doubles are equal you don't need to add the condition <0.000001 this will be covered in else part...) – coder Sep 09 '17 at 10:18
Ok I realized that my starting arrays were not sorted as they were supposed to be. I just solved it, and yes I am no longer using epsilon. Thank you for the help! – osk Sep 09 '17 at 10:23

Merging and sorting two sorted arrays containing doubles in C

1 Answers1