MySQL  8.0.27
Source Code Documentation
merge_sort.h
Go to the documentation of this file.
1 /* Copyright (c) 2012, 2021, Oracle and/or its affiliates.
2 
3  This program is free software; you can redistribute it and/or modify
4  it under the terms of the GNU General Public License, version 2.0,
5  as published by the Free Software Foundation.
6 
7  This program is also distributed with certain software (including
8  but not limited to OpenSSL) that is licensed under separate terms,
9  as designated in a particular file or component or in included license
10  documentation. The authors of MySQL hereby grant you an additional
11  permission to link the program and your derivative works with the
12  separately licensed software that they have included with MySQL.
13 
14  This program is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  GNU General Public License, version 2.0, for more details.
18 
19  You should have received a copy of the GNU General Public License
20  along with this program; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23 
24 #ifndef MERGE_SORT_INCLUDED
25 #define MERGE_SORT_INCLUDED
26 
27 /**
28  @file
29 
30  @brief
31  Merge sort and insert sort implementations. These sorting functions
32  are primarily intended for sorting of JOIN_TABs before the greedy
33  search algorithm is applied. Since the JOIN_TAB comparison functions
34  (Join_tab_compare*) are not transitive, the resulting order depends
35  on the sorting implementation to a certain degree.
36 
37  Since the std::stable_sort and std::sort implementations differ
38  between platforms, the result of sorting JOIN_TABs may also differ.
39  In turn, the query execution plan would differ between platforms and
40  that is a problem with mtr tests (EXPLAIN output would vary).
41 
42  If you intend to sort something transitive (which means almost
43  everything except JOIN_TABs) you should most likely use one of the
44  std sorting functions instead of this.
45 */
46 
47 #include <assert.h>
48 #include <queue>
49 
50 /**
51  Sorts the elements in the range [first,last) into ascending order
52  using insertion sort.
53 
54  @param first First element in an array of pointers to be sorted
55  @param last Element after the last element in an array of pointers
56  to be sorted
57  @param comp Comparison function object that, taking two pointers
58  of the same type as those contained in the range,
59  returns true if the first argument goes before the
60  second argument in the specific strict weak ordering
61  it defines, and false otherwise.
62 
63  In our case comp should be a function object with an operator:
64 
65  bool operator()(Element_type*, Element_type*)
66 */
67 
68 template <typename Element_type, typename Comp_func>
69 void insert_sort(Element_type **first, Element_type **last, Comp_func comp) {
70  for (Element_type **high_water_mark = first + 1; high_water_mark < last;
71  high_water_mark++) {
72  for (Element_type **cur = high_water_mark; cur > first; cur--) {
73  if (comp(*(cur - 1), *cur)) break;
74 
75  Element_type *tmp = *(cur - 1);
76  *(cur - 1) = *cur;
77  *cur = tmp;
78  }
79  }
80 }
81 
82 /**
83  Sorts the elements in the range [first,last) into ascending order
84  using merge sort.
85 
86  @param first First element in an array of pointers to be sorted
87  @param last Element after the last element in an array of pointers
88  to be sorted
89  @param comp Comparison function object that, taking two pointers
90  of the same type as those contained in the range,
91  returns true if the first argument goes before the
92  second argument in the specific strict weak ordering
93  it defines, and false otherwise.
94 
95  In our case comp should be a function object with an operator:
96 
97  bool operator()(Element_type*, Element_type*)
98 */
99 
100 template <typename Element_type, typename Comp_func>
101 void merge_sort(Element_type **first, Element_type **last, Comp_func comp) {
102  const uint elements = static_cast<uint>(last - first);
103 
104  /*
105  Tests showed that the value 5 was a good number for JOIN_TAB
106  ordering, which is the primary use case for this function
107  */
108  if (elements < 5) {
109  insert_sort(first, last, comp);
110  return;
111  }
112  Element_type **middle = first + (elements) / 2;
113 
114  merge_sort(first, middle, comp);
115  merge_sort(middle, last, comp);
116 
117  std::queue<Element_type *> merged;
118 
119  Element_type **cur1 = first;
120  Element_type **cur2 = middle;
121 
122  for (uint i = 0; i < elements; i++) {
123  assert(cur1 < middle || cur2 < last);
124 
125  if (cur1 == middle)
126  merged.push(*cur2++);
127  else if (cur2 == last)
128  merged.push(*cur1++);
129  else if (comp(*cur1, *cur2))
130  merged.push(*cur1++);
131  else
132  merged.push(*cur2++);
133  }
134 
135  Element_type **result = first;
136  while (!merged.empty()) {
137  *result++ = merged.front();
138  merged.pop();
139  }
140 }
141 
142 #endif /* MERGE_SORT_INCLUDED */
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.
Definition: merge_sort.h:69
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.
Definition: merge_sort.h:101
Definition: result.h:29
unsigned int uint
Definition: uca-dump.cc:29