Naive pointer arithmetic merge sort returning errors

Question

Trying to implement a naive merge sort using pointer arithmetic, but it's returning non-sense results. I'm following the convention that l is the leftmost valid index and r is the rightmost valid index.

The input is 5 1 3 2 4 but it returns: 0 1 0 2 5 and naturally the expected output is 1 2 3 4 5.

#include <stdio.h>

void mergeptr(int *array, int l, int m, int r)
{
    int tmp[r - l + 1];
    int *tptr = &(tmp[0]);
    int *lptr = &(array[l]);
    int *rptr = &(array[m]);

    /* Find the smallest in each side */
    while ((lptr < &array[m]) && (rptr < &array[r]))
        if (*lptr <= *rptr) *tptr++ = *lptr++;
        else                *tptr++ = *rptr++;

    /* Copy the remaining */
    while (lptr < &array[m]) *tptr++ = *lptr++;
    while (rptr < &array[r]) *tptr++ = *rptr++;

    /* Copy back */
    for (size_t i = 0; i < (r-l+1); ++i)
        array[l+i] = tmp[i];
}

void merge_sort(int *array, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge_sort(array, l, m);
        merge_sort(array, m + 1, r);
        mergeptr(array, l, m, r);
   }
}

int main(void) { 
    int values[5] = { 5, 1, 3, 2, 4 };

    merge_sort(&values[0], 0, 4);
    for (size_t i = 0; i < 5; ++i)
        printf("%d ", values[i]);
    printf("\n");

    return 0;
}

I have tried to decouple those coupled pointers as *tptr = *lptr; tptr++; lptr++;. To check if something as happening in wrong order but didn't change the outputs. Can't see where the the algorithm is failing.

did you try to debug it? Add some additional printfs in your functions to show you debug trace. That is the way of lerning C — 0___________
– 0___________, Commented Jul 19, 2020 at 9:28
"[32, 52) 'values' (line 34) <== Memory access at offset 52 overflows this variable" — Antti Haapala
– Antti Haapala, Commented Jul 19, 2020 at 9:29

MikeCAT · Accepted Answer · 2020-07-19 10:00:55Z

4

You should be careful when you are dealing with boundaries.
It seems your merge_sort function is dealing with the range [l, r) (including l, excluding r), so:

The element m shouldn't be execluded: merge_sort(array, m+1, r); should be merge_sort(array, m, r);
No sorting is required when there are only 1 element: if (l < r) { should be if (l + 1 < r) {
r - l + 1 and r-l+1 in the function mergeptr should be r - l and r-l.

fixed code:

#include <stdio.h>

void mergeptr(int *array, int l, int m, int r)
{
    int tmp[r - l];
    int *tptr = tmp;
    int *lptr = array + l;
    int *rptr = array + m;

    /* Find the smallest in each side */
    while( (lptr < (array + m)) && (rptr < (array + r)))
        if( *lptr <= *rptr) *tptr++ = *lptr++;
        else                *tptr++ = *rptr++;

    /* Copy the remaining */
    while(lptr < (array + m)) *tptr++ = *lptr++;
    while(rptr < (array + r)) *tptr++ = *rptr++;

    /* Copy back */
    for(size_t i = 0; i < (r-l); ++i)
        array[l+i] = tmp[i];
}

void merge_sort(int *array, int l, int r) {
    if (l + 1 < r) {
        int m = (l+r)/2;
        merge_sort(array, l, m);
        merge_sort(array, m, r);
        mergeptr(array, l, m, r);
   }
}

int main(void) { 
    int values[5] = { 5, 1, 3, 2, 4 };

    merge_sort(values, 0, 5);
    for(size_t i = 0; i < 5; ++i)
        printf("%d ", values[i]);
    printf("\n");

    return 0;
}

edited Jul 19, 2020 at 10:00

answered Jul 19, 2020 at 9:28

MikeCAT

75.1k11 gold badges50 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Sai Over a year ago

&array[r] is undefined behavior right? I guess you need to make some changes?

MikeCAT Over a year ago

@SaiSreenivas Having pointer point at one past the last element should be valid, according to N3337 5.7 Additive operators.

chqrlie Over a year ago

It is a pity so many tutorials and teachers advocate the convention that both boundaries be included. This results in cumbersome and error prone code. Making r excluded allows for much simpler code as can be seen here.

Collectives™ on Stack Overflow

Naive pointer arithmetic merge sort returning errors

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related