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) {
102 const uint elements =
static_cast<uint
>(last - first);
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