CODEWITHSUNDEEP
cpointersmergesort
Lin
Lin

Reputation: 1203

Naive pointer arithmetic merge sort returning errors

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.

Upvotes: 2

Views: 71

Answers (1)

MikeCAT
MikeCAT

Reputation: 75062

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

Upvotes: 4

Related Questions