24#ifndef MERGE_SORT_INCLUDED
25#define MERGE_SORT_INCLUDED
68template <
typename Element_type,
typename Comp_func>
69void insert_sort(Element_type **first, Element_type **last, Comp_func comp) {
70 for (Element_type **high_water_mark = first + 1; high_water_mark <
last;
72 for (Element_type **cur = high_water_mark; cur > first; cur--) {
73 if (comp(*(cur - 1), *cur))
break;
75 Element_type *tmp = *(cur - 1);
100template <
typename Element_type,
typename Comp_func>
101void merge_sort(Element_type **first, Element_type **last, Comp_func comp) {
112 Element_type **middle = first + (elements) / 2;
117 std::queue<Element_type *> merged;
119 Element_type **cur1 = first;
120 Element_type **cur2 = middle;
122 for (
uint i = 0; i < elements; i++) {
123 assert(cur1 < middle || cur2 <
last);
126 merged.push(*cur2++);
127 else if (cur2 ==
last)
128 merged.push(*cur1++);
129 else if (comp(*cur1, *cur2))
130 merged.push(*cur1++);
132 merged.push(*cur2++);
135 Element_type **
result = first;
136 while (!merged.empty()) {
137 *
result++ = merged.front();
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
unsigned int uint
Definition: uca-dump.cc:29