Merge sort 3 way split C

Question

Sorry for annoying anyone here, but I'm having an issue with my merge sort code. Previously I could code the 2-way merge sort and when I tried to adapt my merge sort to be an 3-way merge sort my compiler gave me: 9154 segmentation fault(core dumped). Could you help me to fix this? there is my code:

#include <stdio.h>

void merge(int v[], int p, int q, int r) {
    int i, j, k, b[10];
    for (i = p; i <= q; i++) {
        b[i] = v[i];
    }
    for (j = q + 1; j <= r; j++) {
        b[r + q + 1 - j] = v[j];
    }
    i = p;
    j = r;
    for (k = p; k <= r; k++) {
        if (b[i] <= b[j]) {
            v[k] = b[i];
            i++;
        } else {
            v[k] = b[j];
            j--;
        }
    }
}
void mersort(int v[], int p, int r) { //2-way mergesort that works
    int q;
    if (p < r) {
        q = (p + r) / 2;
        mersort(v, p, q);
        mersort(v, q + 1, r);
        merge(v, p, q, r);
    }
}
void mersort3(int v[], int p, int r) {//not working
    int q, s;
    if (r > p) {
        q = p + (p + r) / 3;
        s = p + 2 * ((p + r) / 3) + 1;
        mersort3(v, p, q);
        mersort3(v, q, s);
        mersort3(v, s, r);
        merge(v, p, q, s);
        merge(v, p, s, r);
    }
}

Your debugger will certainly break on the fault, and the inspection of call stack, base addresses, and index end points, should be a big help in seeing why things broke down. — WhozCraig, Sep 22 '17 at 17:26
I found the problem, but I've tried for 3 days to figure out how to fix it. — Gabriel Andrade, Sep 22 '17 at 17:34
Include whatever sample data you're using to test this as [part of your question](https://stackoverflow.com/posts/46370099/edit), and it obviously cannot exceed 10 elements, or your merge function will overrun indexing and invoke undefined behavior. Also include whatever information you've deciphered in your debugger. You say you know the problem, but seem bent on keeping it private, which isn't constructive. — WhozCraig, Sep 22 '17 at 17:43
You use inclusive upper bounds, which means that in your three-way sort, you treat the elements `q` and `s` twice. You should start the subarrays at `q + 1` and `s + 1` as in yout two-way sort. (I recomment to use exclusive upper bounds as is usual in C; seeing `<=` in loop conditions makes me immediatley wary of the code.) — M Oehm, Sep 22 '17 at 18:16
Your error is an infinite recutsion, for example when `p == 2`and `r == 3`, then `q == p + (p + r) / 3 == 3`. You then call `sort(2, 3)`. Ooopsie. What's worse: `s == p + 2 * (p + r) / 3 + 1 == 6`, which is out of the bounds of the range to be sorted. Surely you mean `q = p + (r - p) / 3`. — M Oehm, Sep 22 '17 at 18:17

score 2 · Answer 1 · answered Sep 22 '17 at 18:23

Your main problems are due to out-of-range indexing due to improper index calculations, and potential infinite recursion for the same reason.

You're overcomplicating this tremendously. One of the beautiful advantages to C is pointer arithmetic, which makes things like sequence partitioning and traversals like this much, much simpler. As a bonus, you also get to remove one of your function arguments, as the only reason it is there is the base-adjustment, which is taken care of with the pointer arithmetic.

For example, a simple VLA-based merge algorithm (obviously, don't invoke this with a large sequence)

/* a simple little VLA-based merge. don't invoke with huge arrays */
void merge(int v[], size_t mid, size_t len)
{
    if (len < 2)
        return;

    size_t i=0, j=mid, k=0;
    int tmp[len];

    while (i < mid && j < len)
        tmp[k++] = (v[i] < v[j]) ? v[i++] : v[j++];

    memcpy(tmp+k, v+i, (mid-i) * sizeof *v);
    memcpy(v, tmp, (k + (mid-i)) * sizeof *v);
}

Well, not a great showcase of pointer arithmetic, but there's some in there. The place where it really shines is the partitioning algorithms. For example, a simple merge sort:

void mersort(int v[], size_t len)
{
    if (len < 2)
        return;

    size_t mid = len/2;
    mersort(v, mid);
    mersort(v+mid, len-mid); // see here.
    merge(v, mid, len);
}

Extending this to a three-way partitioning scheme becomes:

void mersort3(int v[], size_t len)
{
    if (len < 3)
    {
        mersort(v, len);
        return;
    }

    size_t m1 = len/3;
    size_t m2 = (2 * len)/3;
    mersort3(v, m1);
    mersort3(v+m1, m2-m1);   // see here
    mersort3(v+m2, len-m2);  // and here
    merge(v, m1, m2);
    merge(v, m2, len);
}

An example invoke that uses a guaranteed-unusual partition size is below (the sequence is 29 elements long)

int main()
{
    srand((unsigned)time(NULL));

    const size_t N = 29;
    size_t i,j;
    int ar[N], n=0;

    // build a sequence from 1..29
    for (i=0; i<N; ++i)
        ar[i] = ++n;

    // shuffle the sequence
    for (i=0; i<3; ++i)
    {
        for (j=0; j<N; ++j)
        {
            n = rand() % N;
            int tmp = ar[n];
            ar[n] = ar[j];
            ar[j] = tmp;
        }
    }

    // show the shuffled sequence
    for (i=0; i<N; ++i)
        printf("%d ", ar[i]);
    fputc('\n', stdout);

    // sort it
    mersort3(ar, N);

    // show it again
    for (i=0; i<N; ++i)
        printf("%d ", ar[i]);
    fputc('\n', stdout);

    return EXIT_SUCCESS;
}

Output (shuffled sequence varies)

21 8 11 27 18 9 17 28 20 14 15 1 29 6 19 22 7 2 16 23 5 12 4 3 10 26 13 25 24 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Merge sort 3 way split C

1 Answers1