HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Bottom up (iterative) mergesort in C

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
bottommergesortiterative

Problem

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

mergesort.h:

#ifndef MERGESORT_H
#define MERGESORT_H

#include 

#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
#include

#define MIN(a,b) ((a) > 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 >= 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,

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#131878, answer score: 2

Revisions (0)

No revisions yet.