merge_sort.h File Reference

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. More...

#include "sql_select.h"
#include <queue>

Include dependency graph for merge_sort.h:

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

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)
template<typename Element_type , typename Comp_func >
void	merge_sort (Element_type **first, Element_type **last, Comp_func comp)

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.

Definition in file merge_sort.h.

Function Documentation

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*)

Definition at line 62 of file merge_sort.h.

Here is the caller graph for this function:

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*)

Definition at line 100 of file merge_sort.h.

Here is the call graph for this function:

Here is the caller graph for this function: