MySQL  8.0.27
Source Code Documentation
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
firstFirst element in an array of pointers to be sorted
lastElement after the last element in an array of pointers to be sorted
compComparison 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
firstFirst element in an array of pointers to be sorted
lastElement after the last element in an array of pointers to be sorted
compComparison 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*)