Merge Sort without pointers in C

Question

As part of an online course exercise, I was supposed to implement Merge Sort in C. Pointers were still not discussed prior to this exercise, so I have to work with arrays. Memory efficiency is not something I'm supposed to be focused on.

#include <cs50.h>
#include <stdio.h>

#define DEBUG

void getArray(int[], int);
void printArray(int[], int);
void mergesort(int[], int);
void merge(int[], int, int[], int, int[]);

int main(void)
{
    printf("Length of array: ");
    int len = GetInt();

    int array[len];
    getArray(array, len);

    printf("Before sort: ");
    printArray(array, len);

    mergesort(array, len);

    printf("After sort: ");
    printArray(array, len);

    return 0;
}

void getArray(int values[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("Number %i: ", i + 1);
        values[i] = GetInt();
    }
}

void printArray(int values[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%i ", values[i]);
    }

    printf("\n");
}

void mergesort(int array[], int len)
{
    if (len <= 1)
        return;

    // right side and left side lengths
    int rlen, llen;

    //calculate lengths of the half-arrays
    rlen = len / 2;
    llen = len - rlen;

    int rhalf[rlen];
    int lhalf[llen];

    // copy first half of array into rhalf
    for (int i = 0; i < rlen; i++)
    {
        rhalf[i] = array[i];
    }

    // copy the remainder of array into lhalf
    for (int i = 0; i < llen; i++)
    {
        lhalf[i] = array[i + rlen];
    }

    #ifdef DEBUG
        printf("len: %i\nrlen: %i\nllen: %i\n", len, rlen, llen);
        printf("rhalf: ");
        printArray(rhalf, rlen);
        printf("lhalf: ");
        printArray(lhalf, llen);
    #endif

    mergesort(rhalf, rlen);
    mergesort(lhalf, llen);
    merge(rhalf, rlen, lhalf, llen, array);
}

void merge(int rhalf[], int rlen, int lhalf[], int llen, int array[])
{
    int i = 0, j = 0, k = 0;

    // iterate over rhalf and lhalf until one counter reaches its end
    while (i < rlen && j < llen)
    {
        if (rhalf[i] < lhalf[j])
        {
            array[k] = rhalf[i];
            i++;
        }

        else
        {
            array[k] = lhalf[j];
            j++;
        }

        k++;
    }

    // place the remaining elements (if any) in either half in their place
    while (i < rlen)
    {
       array[k] = rhalf[i];
       i++;
       k++;
    }

    while (j < llen)
    {
        array[k] = lhalf[j];
        j++;
        k++;
    }

    #ifdef DEBUG
        printf("merged: ");
        printArray(array, llen + rlen);
    #endif
}

What can I do to improve the code in terms of readability, style and performance?

coderodde · Accepted Answer · 2015-09-07 06:33:52Z

What comes to performance, in order to merge two subranges, you copy them first and then merge. All in all, you make \$\Theta(n \log n)\$ array component copies. One thing to remedy this is to allocate the entire range before actual sorting, copy the input array contents to it and proceed making the array swapping: at one recursion level, you merge from one array to another, at the next recursion level you merge in opposite direction. See what I mean:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void getArray(int* values, int len)
{
    for (int i = 0; i < len; i++)
    {
        values[i] = rand() % 100;
    }
}

static void printArray(int* values, int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%i ", values[i]);
    }

    printf("\n");
}

static void merge(int* source_left,
                  int* source_middle,
                  int* source_end,
                  int* target) 
{
    int* left      = source_left;
    int* right     = source_middle;
    int* left_end  = source_middle;
    int* right_end = source_end;

    while (left < left_end && right < right_end) 
    {
        *target++ = *left < *right ?  *left++ : *right++;
    }

    while (left < left_end) *target++ = *left++;
    while (right < right_end) *target++ = *right++;
}

static void mergesort_impl(int* source, int* target, int len)
{
    if (len < 2) return;

    int left_range_length = len / 2;
    /* No copying here whatsoever. */
    mergesort_impl(target, 
                   source, 
                   left_range_length);

    mergesort_impl(target + left_range_length, 
                   source + left_range_length,
                   len - left_range_length);

    merge(source, 
          source + left_range_length,
          source + len,
          target);
}

static void mergesort_(int* array, int len)
{
    if (len <= 1) return;

    int* aux = malloc(sizeof(int) * len);
    memcpy(aux, array, sizeof(int) * len);
    mergesort_impl(aux, array, len);
    free(aux);
}

int main(void)
{
    int len = 10;
    srand(time(NULL));

    int* array = malloc(sizeof(int) * len);
    getArray(array, len);

    printf("Before sort: ");
    printArray(array, len);

    mergesort_(array, len);

    printf("After sort: ");
    printArray(array, len);

    return 0;
}

Community · Accepted Answer · 2020-06-10 13:24:26Z

Variable length arrays

In your program, you use variable length arrays for all your arrays. These are typically allocated on the stack, which is usually limited in size. When I ran your program on an input of 200000 numbers, the program crashed on my system. By my calculation, you use one full length array for the original array, plus up to 2x extra space when allocating the temporary arrays for merging. So that means your program was attempting to put 600000 ints, or 2.4 MB, on the stack.

I would suggest allocating your arrays using malloc() instead. This puts the arrays on the heap, which is normally much larger than the stack. Also, there is a way you can only use 1x the temporary space instead of 2x, if you only allocate the temporary in your merge function instead of in your sort function. The sort function would look sort of like this:

mergesort(array, 0, mid);
mergesort(&array[mid+1], len-mid);
merge(array, 0, mid, len);

But perhaps since you haven't learned about pointers, you didn't know you could pass the middle of an array to a function.

`memcpy`

You do some manually array copying here:

// copy first half of array into rhalf
for (int i = 0; i < rlen; i++)
{
    rhalf[i] = array[i];
}

You could use the standard library function memcpy() to do this instead. It probably will run faster than your loop because it is optimized to run fast:

memcpy(rhalf, array, rlen * sizeof(int));

Stack Exchange Network

Merge Sort without pointers in C

2 Answers 2

Variable length arrays

`memcpy`

You must log in to answer this question.

Hot Network Questions

Merge Sort without pointers in C

2 Answers 2

Variable length arrays

memcpy

You must log in to answer this question.

Related

Hot Network Questions

`memcpy`