cgul_merge_sort.h File Reference

merge sort More...

#include "cgul_common.h"
#include "cgul_exception.h"

Include dependency graph for cgul_merge_sort.h:

This graph shows which files directly or indirectly include this file:

Functions
CGUL_EXPORT void	cgul_merge_sort (cgul_exception_t *cex, void *v, size_t v_count, size_t element_size, cgul_merge_sort__compare_t cf)
CGUL_EXPORT void	cgul_merge_sort_iteratively (cgul_exception_t *cex, void *v, size_t v_count, size_t element_size, cgul_merge_sort__compare_t cf)
CGUL_EXPORT void	cgul_merge_sort_pointers (cgul_exception_t *cex, void **v, size_t v_count, cgul_merge_sort__compare_t cf)
CGUL_EXPORT void	cgul_merge_sort_pointers_iteratively (cgul_exception_t *cex, void **v, size_t v_count, cgul_merge_sort__compare_t cf)

Variables
CGUL_BEGIN_C typedef int(*	cgul_merge_sort__compare_t )(const void *e1, const void *e2)

Detailed Description

Merge sort an array.

Author

Paul Serice

Function Documentation

cgul_merge_sort()

CGUL_EXPORT void cgul_merge_sort	(	cgul_exception_t *	cex,
		void *	v,
		size_t	v_count,
		size_t	element_size,
		cgul_merge_sort__compare_t	cf
	)

Generic in-place sort with the same parameter signature as stdlib's qsort(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. cf is the comparison function. It will be passed pointers to two elements. It must return less than zero, zero, or greater than zero if the first element is less than, equal to, or greater than the second element. This function has to internally allocate memory to perform its task. If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.

The main draw back to using merge sort when sorting arrays is that it needs to create a copy of the original array in order to work efficiently. This particular implementation actually requires 1.5 copies of the original array at peak memory usage. If you are short on memory, you can either use cgul_merge_sort_iteratively() which only requires 1 copy or cgul_list__sort() which requires no extra copies because it operates on linked lists which have efficient removal and insertion operations.

If you need to constantly maintain a sorted list, cgul_rbtree or cgul_multimap are usually better solutions.

Parameters

[in,out]	cex	c-style exception
[in]	v	array of elements to sort
[in]	v_count	number of elements in v
[in]	element_size	size of each element in v (in bytes)
[in]	cf	comparison function

Referenced by cgul_merge_sort_cxx::sort().

cgul_merge_sort_iteratively()

CGUL_EXPORT void cgul_merge_sort_iteratively	(	cgul_exception_t *	cex,
		void *	v,
		size_t	v_count,
		size_t	element_size,
		cgul_merge_sort__compare_t	cf
	)

Generic in-place sort with the same parameter signature as stdlib's qsort(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. cf is the comparison function. It will be passed pointers to two elements. It must return less than zero, zero, or greater than zero if the first element is less than, equal to, or greater than the second element. This function has to internally allocate memory to perform its task. If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.

There are three main differences between this function and cgul_merge_sort(). First, cgul_merge_sort() is about 30% faster than this function. Second, cgul_merge_sort() is a recursive implementation that consumes more stack space than this function which is an iterative implementation. Third, cgul_merge_sort() uses 50% more memory than this implementation because it requires 1.5 extra copies of v; whereas, this implementation only requires 1 extra copy. If in doubt, use cgul_merge_sort() instead of this function.

If you need to constantly maintain a sorted list, cgul_rbtree or cgul_multimap are usually better solutions.

Parameters

[in,out]	cex	c-style exception
[in]	v	array of elements to sort
[in]	v_count	number of elements in v
[in]	element_size	size of each element in v (in bytes)
[in]	cf	comparison function

Referenced by cgul_merge_sort_cxx::sort_iteratively().

cgul_merge_sort_pointers()

CGUL_EXPORT void cgul_merge_sort_pointers	(	cgul_exception_t *	cex,
		void **	v,
		size_t	v_count,
		cgul_merge_sort__compare_t	cf
	)

If your array is already composed of pointers, you can directly call this function. v will be sorted using cf the same as described for cgul_merge_sort(). If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.

The main draw back to using merge sort when sorting arrays is that it needs to create a copy of the original array in order to work efficiently. This particular implementation actually requires 1.5 copies of the original array at peak memory usage. If you are short on memory, you can either use cgul_merge_sort_pointers_iteratively() which only requires 1 copy or cgul_list__sort() which requires no extra copies because it operates on linked list which have efficient removal and insertion operations.

If you need to constantly maintain a sorted list, cgul_rbtree or cgul_multimap are usually better solutions.

Parameters

[in,out]	cex	c-style exception
[in]	v	array of pointers to elements to sort
[in]	v_count	number of elements in v
[in]	cf	comparison function

Referenced by cgul_merge_sort_cxx::sort_pointers().

cgul_merge_sort_pointers_iteratively()

CGUL_EXPORT void cgul_merge_sort_pointers_iteratively	(	cgul_exception_t *	cex,
		void **	v,
		size_t	v_count,
		cgul_merge_sort__compare_t	cf
	)

If your array is already composed of pointers, you can directly call this function. v will be sorted using cf the same as described for cgul_merge_sort_iteratively(). If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.

There are three main differences between this function and cgul_merge_sort_pointers(). First, cgul_merge_sort_pointers() is about 30% faster than this function. Second, cgul_merge_sort_pointers() is a recursive implementation that consumes more stack space than this function which is an iterative implementation. Third, cgul_merge_sort_pointers() uses 50% more memory than this implementation because it requires 1.5 extra copies of v; whereas, this implementation only requires 1 extra copy. If in doubt, use cgul_merge_sort_pointers() instead of this function.

If you need to constantly maintain a sorted list, cgul_rbtree or cgul_multimap are usually better solutions.

Parameters

[in,out]	cex	c-style exception
[in]	v	array of pointers to elements to sort
[in]	v_count	number of elements in v
[in]	cf	comparison function

Referenced by cgul_merge_sort_cxx::sort_pointers_iteratively().

Variable Documentation

cgul_merge_sort__compare_t

CGUL_BEGIN_C typedef int(* cgul_merge_sort__compare_t) (const void *e1, const void *e2)

This typedef is the interface the client must define in order for cgul_merge_sort() or cgul_merge_sort_pointers() to sort an array. When defining the comparison function, it should compare e1 to e2 and return less than zero, zero, or greater than zero if e1 is less than, equal to, or greater than e2.

Parameters

[in]	e1	first element
[in]	e2	second element

Returns

result of comparison