patterncMinor
Bottom up (iterative) mergesort in C
Viewed 0 times
bottommergesortiterative
Problem
I have this C implementation of the bottom-up (iterative) mergesort:
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,
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
all references to the function pointer
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:
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: 1Code Snippets
my_mergesort took 3091 milliseconds.
qsort took 2156 milliseconds.
bottom_up_mergesort took 3009 milliseconds.
Arrays are identical: 1Context
StackExchange Code Review Q#131878, answer score: 2
Revisions (0)
No revisions yet.