4
\$\begingroup\$

I have this C implementation of the bottom-up (iterative) mergesort:

mergesort.h:

#ifndef MERGESORT_H
#define MERGESORT_H

#include <stdlib.h>

#ifdef  __cplusplus
extern "C" {
#endif

    void my_mergesort(void* base, 
                      size_t num, 
                      size_t size, 
                      int (*compar)(const void*, const void*));

    void bottom_up_mergesort(const void* base,
                             const size_t num,
                             const size_t size,
                             const int (*compar)(const void*, const void*));

#ifdef  __cplusplus
}
#endif

#endif  /* MERGESORT_H */

mergesort.c:

#include "mergesort.h"
#include <stdlib.h>
#include <string.h>

#define MIN(a,b) ((a) < (b) ? (a) : (b))

static void mergesort_impl(void* source,
                           void* target,
                           size_t size,
                           size_t offset,
                           size_t range_length,
                           int (*compar)(const void*, const void*)) 
{
    if (range_length < 2) 
    {
        return;
    }

    size_t half_range_length = range_length >> 1;

    mergesort_impl(target, 
                   source,
                   size, 
                   offset, 
                   half_range_length,
                   compar);

    mergesort_impl(target, 
                   source,
                   size, 
                   offset + half_range_length, 
                   range_length - half_range_length,
                   compar);

    void* left_subarray_pointer = source + offset * size;
    void* left_subarray_pointer_bound = left_subarray_pointer +
                                        half_range_length * size;

    void* right_subarray_pointer = left_subarray_pointer_bound;
    void* right_subarray_pointer_bound = source + (offset + range_length) 
                                                * size;

    void* target_array_pointer = target + offset * size;

    while (left_subarray_pointer < left_subarray_pointer_bound
            && right_subarray_pointer < right_subarray_pointer_bound) 
    {
        if (compar(right_subarray_pointer, left_subarray_pointer) < 0)
        {
            memcpy(target_array_pointer, right_subarray_pointer, size);
            target_array_pointer   += size;
            right_subarray_pointer += size;
        }
        else 
        {
            memcpy(target_array_pointer, left_subarray_pointer, size);
            target_array_pointer  += size;
            left_subarray_pointer += size;
        }
    }

    memcpy(target_array_pointer, 
           left_subarray_pointer, 
           left_subarray_pointer_bound - left_subarray_pointer);

    memcpy(target_array_pointer, 
           right_subarray_pointer, 
           right_subarray_pointer_bound - right_subarray_pointer);
}

void my_mergesort(void* base, 
                  size_t num, 
                  size_t size, 
                  int (*compar)(const void*, const void*))
{
    void* aux = malloc(num * size);
    memcpy(aux, base, num * size);
    mergesort_impl(aux, base, size, 0, num, compar);
    free(aux);
}

size_t compute_number_of_merge_passes(size_t size)
{
    size--;

    const size_t size_t_bits = 8 * sizeof(size_t);
    size_t mask = ((size_t) 1) << (size_t_bits - 1);

    for (size_t i = 0; i < size_t_bits; ++i, mask >>= 1) 
    {
        if (mask & size)
        {
            return size_t_bits - i;
        }
    }

    // We should not get here, ever.
    abort();
}

static void merge(const void* source,
                  const void* target,
                  const size_t size,
                  const size_t left_run_length,
                  const size_t right_run_length,
                  const int (*compar)(const void*, const void*))
{
    void* left_run_ptr  = (void*) source;
    void* right_run_ptr = (void*) source + left_run_length * size;

    const void* left_run_bound  = right_run_ptr;
    const void* right_run_bound = left_run_bound + right_run_length * size;

    while (left_run_ptr < left_run_bound
            && right_run_ptr < right_run_bound) 
    {
        if (compar(right_run_ptr, left_run_ptr) < 0)
        {
            memcpy((void*) target, right_run_ptr, size);
            target        += size;
            right_run_ptr += size;
        }
        else
        {
            memcpy((void*) target, left_run_ptr, size);
            target       += size;
            left_run_ptr += size;
        }
    }

    memcpy((void*) target,
           left_run_ptr, 
           left_run_bound - left_run_ptr);

    memcpy((void*) target, 
           right_run_ptr, 
           right_run_bound - right_run_ptr);
}

/*******************************************************************************
******************************************************************************** 
* source     - the array from which to take the elements.                      *
* target     - the array to which to merge the results.                        *
* num        - the total number of elements in the requested sorting range.    *
* size       - the size of an array element in bytes.                          *
* run_length - the current size of the runs being merged.                      *
* runs       - total number of runs at this recursion level.                   *
* compar     - the element comparator function.                                *
*******************************************************************************/
static void merge_pass(const void* source,
                       const void* target,
                       const size_t num,
                       const size_t size,
                       const size_t run_length,
                       const size_t runs,
                       const int (*compar)(const void*, const void*))
{   
    // [INFO] 'runs' is guaranteed to be at least 2!
    if (runs & 1)
    {
        // [STATE] Once here, we have an odd number of runs. This implies that 
        // the leftmost '(runs - 1)' are all of equal length, and since 
        // 'runs - 1' is even, we have '(runs - 1) / 2' amount of run pairs.
        // In the following loop, we merge the '(runs - 1) / 2' run pairs.
        for (size_t run_index = 0; run_index < runs - 1; run_index += 2)
        {
            merge(source,
                  target,
                  size,
                  run_length,
                  run_length,
                  compar);

            // Advance the run points over the two runs we just merged.
            source += (size * run_length) << 1;
            target += (size * run_length) << 1;
        }

        // Here we deal with the remaining "orphan" run. We must copy it to 
        // 'target' as it may be present in the end of 'target' as two sorted
        // unmerged runs.
        memcpy((void*) target, 
               source, 
               size * (num - run_length * (runs - 1)));
        return;
    }

    // [STATE] Once here, 'runs' is an even integer with value at least 2.
    // This implies that the very last run may have smaller length than 
    // 'run_length'.
    size_t run_index = 0;

    // Omit 2 last runs, since the very last run is not guaranteed to be of
    // length 'run_length': its length may be less than 'run_length'. We 
    // "unroll" this loop in order to eliminate the code that needs to fix the
    // length of the very last run.
    for (; run_index < runs - 2; run_index += 2)
    {
        merge(source,
              target,
              size,
              run_length,
              run_length,
              compar);

        source += (size * run_length) << 1;
        target += (size * run_length) << 1;
    }

    // Here we deal with the very last pair of runs, in which the length of the
    // last run may be smaller than 'run_length'.
    const size_t last_run_length = MIN(run_length, 
                                       num - run_length * (runs - 1));

    merge(source,
          target,
          size,
          run_length,
          last_run_length,
          compar);
}

void bottom_up_mergesort(const void* base,
                         const size_t num,
                         const size_t size,
                         const int (*compar)(const void*, const void*))
{
    if (num < 2)
    {
        // Trivially sorted.
        return;
    }

    size_t number_of_merge_passes = compute_number_of_merge_passes(num);

    void* aux = malloc(num * size);

    void* source;
    void* target;
    void* tmp_array;

    if (number_of_merge_passes & 1)
    {
        // Copy the contents of 'base' to 'aux' since in the very first merge
        // pass we will be reading the elements from 'aux'.
        memcpy(aux, base, num * size);
        source = aux;
        target = (void*) base;
    }
    else
    {
        // Here we do not need to copy the contents of 'base' to 'aux', since
        // we will begin merging from 'base' to 'aux'.
        source = (void*) base;
        target = aux;
    }

    size_t runs = num;

    // Do the actual merge passes over the data:
    for (size_t run_length = 1; run_length < num; run_length <<= 1) 
    {
        merge_pass(source,
                   target, 
                   num, 
                   size, 
                   run_length,
                   runs,
                   compar);

        // Swap array roles:
        tmp_array = source;
        source = target;
        target = tmp_array;

        // Update the number of runs left:
        runs = (runs >> 1) + ((runs & 1) ? 1 : 0);
    }

    free(aux);
}

main.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include "mergesort.h"

static int compar(const void* a, const void* b) 
{
    return (*(int*) a) - (*(int*) b);
}

static int* create_random_int_array(size_t length)
{
    int* array = malloc(length * sizeof(int));

    srand(time(NULL));

    for (size_t i = 0; i < length; ++i) 
    {
        array[i] = rand() % (1000 * 1000);
    }

    return array;
}

static long get_milliseconds() 
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

int arrays_are_same(int* arr1, int* arr2, size_t length) 
{
    for (size_t i = 0; i < length; ++i) 
    {
        if (arr1[i] != arr2[i]) 
        {
            return 0;
        }
    }

    return 1;
}

static const size_t ARRAY_SIZE = 10 * 1000 * 1000 + 3;

int main() {
    int* arr1 = create_random_int_array(ARRAY_SIZE);
    int* arr2 = malloc(sizeof(int) * ARRAY_SIZE);
    int* arr3 = malloc(sizeof(int) * ARRAY_SIZE);

    memcpy(arr2, arr1, sizeof(int) * ARRAY_SIZE);
    memcpy(arr3, arr1, sizeof(int) * ARRAY_SIZE);

      //////////////////////
     //// my_mergesort ////
    //////////////////////
    long start_time = get_milliseconds();
    my_mergesort(arr1, ARRAY_SIZE, sizeof(int), compar);
    long end_time = get_milliseconds();
    printf("my_mergesort took %ld milliseconds.\n", end_time - start_time);

      ///////////////
     //// qsort ////
    ///////////////
    start_time = get_milliseconds();
    qsort(arr2, ARRAY_SIZE, sizeof(int), compar);
    end_time = get_milliseconds();
    printf("qsort took %ld milliseconds.\n", end_time - start_time);

      /////////////////////////////
     //// bottom_up_mergesort ////
    /////////////////////////////
    start_time = get_milliseconds();
    bottom_up_mergesort((void*) arr3, 
                        ARRAY_SIZE, 
                        sizeof(int), 
                        (const int (*)(const void*, const void*)) compar);
    end_time = get_milliseconds();
    printf("bottom_up_mergesort took %ld milliseconds.\n", 
           end_time - start_time);

      /////////////////////////
     //// Compare results ////
    /////////////////////////
    printf("Arrays are identical: %d\n", 
            arrays_are_same(arr1, arr2, ARRAY_SIZE) &&
            arrays_are_same(arr1, arr3, ARRAY_SIZE));

    free(arr1);
    free(arr2);
    free(arr3);
}

Any critique is much appreciated.

\$\endgroup\$
2
  • \$\begingroup\$ Is this faster than the last version? \$\endgroup\$ – pacmaninbw Jun 14 '16 at 13:31
  • \$\begingroup\$ @pacmaninbw Yes, but by a very small margin. Actually, I just wanted to see the actual performance figures of the bottom-up mergesort. \$\endgroup\$ – coderodde Jun 15 '16 at 9:57
2
\$\begingroup\$

the posted code does not cleanly compile.

When compiling, always enable all the warnings, then fix those warnings.

(for gcc, at a minimum use: -Wall -Wextra -pedantic I also use: -Wconversion -std-gnu99 )

all references to the function pointer (*compar) should have the 'const' modifier removed. As it is, the compiler will ignore that modifier

It is a poor programming practice to pass the address of static functions.

The compiler will output several warnings about conversions between different types of integer values (unsigned, signed, long, etc) These should be corrected.

When calling any of the memory allocation functions: (malloc, calloc, realloc), always check (!=NULL) to assure the operation was successful.

I'm running linux 14.04.4 on a AMD A8-7650K Radeon R7, 10 Compute Cores 4C+6G × 4

Here is the output from a typical run of the program:

my_mergesort took 3091 milliseconds.
qsort took 2156 milliseconds.
bottom_up_mergesort took 3009 milliseconds.
Arrays are identical: 1
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.