merge_sort.h File Reference

Merge sort and insert sort implementations. More...

#include <assert.h>
#include <queue>

Go to the source code of this file.

Functions
template<typename Element_type , typename Comp_func >
void	insert_sort (Element_type **first, Element_type **last, Comp_func comp)
	Sorts the elements in the range [first,last) into ascending order using insertion sort. More...
template<typename Element_type , typename Comp_func >
void	merge_sort (Element_type **first, Element_type **last, Comp_func comp)
	Sorts the elements in the range [first,last) into ascending order using merge sort. More...

Detailed Description

Merge sort and insert sort implementations.

These sorting functions are primarily intended for sorting of JOIN_TABs before the greedy search algorithm is applied. Since the JOIN_TAB comparison functions (Join_tab_compare*) are not transitive, the resulting order depends on the sorting implementation to a certain degree.

Since the std::stable_sort and std::sort implementations differ between platforms, the result of sorting JOIN_TABs may also differ. In turn, the query execution plan would differ between platforms and that is a problem with mtr tests (EXPLAIN output would vary).

If you intend to sort something transitive (which means almost everything except JOIN_TABs) you should most likely use one of the std sorting functions instead of this.

Function Documentation

insert_sort()

template<typename Element_type , typename Comp_func >

void insert_sort	(	Element_type **	first,
		Element_type **	last,
		Comp_func	comp
	)

Sorts the elements in the range [first,last) into ascending order using insertion sort.

Parameters

first	First element in an array of pointers to be sorted
last	Element after the last element in an array of pointers to be sorted
comp	Comparison function object that, taking two pointers of the same type as those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

In our case comp should be a function object with an operator:

bool operator()(Element_type*, Element_type*)

merge_sort()

template<typename Element_type , typename Comp_func >

void merge_sort	(	Element_type **	first,
		Element_type **	last,
		Comp_func	comp
	)

Sorts the elements in the range [first,last) into ascending order using merge sort.

Parameters

first	First element in an array of pointers to be sorted
last	Element after the last element in an array of pointers to be sorted
comp	Comparison function object that, taking two pointers of the same type as those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.

In our case comp should be a function object with an operator:

bool operator()(Element_type*, Element_type*)