1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
27 // File: vogl_introsort.h
28 // Rewritten for competitive performance vs. glibc's std::sort by Rich Geldreich.
29 // Original author was Keith Schwarz (htiek@cs.stanford.edu), appeared on his website like this:
30 // "If you're interested in using any of this code in your applications, feel free to
31 // do so! You don't need to cite me or this website as a source, though I would appreciate
34 // Needed for independence from any particular RTL, and because glibc's
35 // std::sort is now optimized for std::move. When not compiling for
36 // C++0x11 std::sort doesn't actually use std::swap, and all my stuff overloads
37 // std::swap for perf. So screw glibc.
38 // I've optimized this to compete against glib'c introsort, and
39 // eliminated the dependence on std::make_heap/sort_heap.
40 // Most importantly, the original pivot code was subtly flawed (way too many swaps).
41 // It's within +- ~1% of glibc's std::sort on int arrays.
42 #ifndef VOGL_INTROSORT_H
43 #define VOGL_INTROSORT_H
45 #include "vogl_core.h"
49 template <typename RandomIterator>
50 void introsort(RandomIterator begin, RandomIterator end);
52 template <typename RandomIterator, typename Comparator>
53 void introsort(RandomIterator begin, RandomIterator end, Comparator comp);
55 namespace introsort_detail
57 template <class ForwardIt1, class ForwardIt2>
58 inline void introsort_iter_swap(ForwardIt1 a, ForwardIt2 b)
64 template <typename T, typename F>
65 inline void heapsort_helper(size_t size, T *a, F compare_func)
70 size_t start = (size - 1 - 1) >> 1;
77 size_t child = (root << 1) + 1;
81 if (((child + 1U) < size) && (compare_func(a[child], a[child + 1])))
84 if (compare_func(a[root], a[child]))
86 std::swap(a[root], a[child]);
99 size_t end = size - 1;
102 std::swap(a[end], a[0]);
108 size_t child = (root << 1) + 1;
112 if (((child + 1U) < end) && (compare_func(a[child], a[child + 1])))
115 if (compare_func(a[root], a[child]))
117 std::swap(a[root], a[child]);
130 template <typename RandomIterator, typename Comparator>
131 inline void heapsort(RandomIterator begin, RandomIterator end, Comparator comp, size_t num_elems)
133 VOGL_NOTE_UNUSED(end);
134 heapsort_helper(num_elems, begin, comp);
137 template <typename RandomIterator, typename Comparator>
138 inline void heapsort(RandomIterator begin, RandomIterator end, Comparator comp)
140 heapsort(begin, end, comp, std::distance(begin, end));
143 template <typename RandomIterator>
144 inline void heapsort(RandomIterator begin, RandomIterator end)
146 heapsort(begin, end, std::less<typename std::iterator_traits<RandomIterator>::value_type>());
149 // Important: Don't mess with this guy or you can subtly regress perf!
150 template <typename RandomIterator, typename Comparator>
151 inline RandomIterator partition(RandomIterator begin, RandomIterator end, Comparator comp)
153 RandomIterator lhs = begin + 1;
154 RandomIterator rhs = end;
155 const typename std::iterator_traits<RandomIterator>::value_type &pivot = *begin;
159 // This is guaranteed to terminate within range because pivot is the median of 3 elements from the partition, so there must be an element >= pivot within the partition.
160 while (comp(*lhs, pivot))
165 // This is guaranteed to terminate within range because when rhs is begin (the pivot location) comp(pivot, pivot) is guaranteed to return false.
166 while (comp(pivot, *rhs))
172 introsort_iter_swap(lhs, rhs);
177 // Swaps the median element to one.
178 template <typename RandomIterator, typename Comparator>
179 inline void median_of_three(RandomIterator one, RandomIterator two, RandomIterator three, Comparator comp)
181 const bool comp12 = comp(*one, *two);
182 const bool comp23 = comp(*two, *three);
184 if (comp12 && comp23)
187 introsort_iter_swap(two, one);
191 const bool comp13 = comp(*one, *three);
193 if (comp12 && !comp23 && comp13)
196 introsort_iter_swap(three, one);
200 if (!comp12 && comp13)
206 if (!comp12 && !comp13 && comp23)
209 introsort_iter_swap(three, one);
213 if (comp12 && !comp13)
220 introsort_iter_swap(two, one);
223 template <typename RandomIterator, typename Comparator>
224 inline void insertion_sort(RandomIterator begin, RandomIterator end, Comparator comp)
229 for (RandomIterator itr = begin + 1; itr != end; ++itr)
231 for (RandomIterator test = itr; test != begin && comp(*test, *(test - 1)); --test)
232 introsort_iter_swap(test, test - 1);
236 template <typename RandomIterator, typename Comparator>
237 void introsort_rec(RandomIterator begin, RandomIterator end, size_t depth, Comparator comp)
239 const size_t kBlockSize = 16;
243 const size_t numElems = size_t(end - begin);
245 if (numElems < kBlockSize)
247 // Seems a tiny bit faster to immediately do the insertion on the partition.
248 // Also avoids compares between partitions, which we know are already sorted
249 // relative to eachother.
250 insertion_sort(begin, end, comp);
256 heapsort(begin, end, comp, numElems);
260 median_of_three(begin, begin + (numElems >> 1), end - 1, comp);
264 RandomIterator partition_point = introsort_detail::partition(begin, end, comp);
266 // This is consistently slower on cheap objects (int)'s - dunno why yet.
267 RandomIterator pivot_iter = partition_point - 1;
269 // Move the pivot element into its final sorted position.
270 if (pivot_iter != begin)
271 introsort_iter_swap(begin, pivot_iter);
273 // Now all elements < partition_point are <= the pivot element,
274 // and all elements >= partition_point are >= the pivot element,
275 // and the element right before partition_point (the pivot element)
276 // is in its final sorted position so we can exclude it from
279 for (RandomIterator it = partition_point; it < end; ++it)
280 VOGL_ASSERT(utils::compare_ge(*it, *pivot_iter, comp));
282 for (RandomIterator it = begin; it < partition_point; ++it)
283 VOGL_ASSERT(utils::compare_le(*it, *pivot_iter, comp));
286 // Recurse into the smaller subpartition, tail call to larger.
287 // Not a win on random int arrays, but a small win on complex objects.
288 if ((pivot_iter - begin) < (end - (pivot_iter + 1)))
290 introsort_rec(begin, pivot_iter, depth, comp);
291 begin = pivot_iter + 1;
295 introsort_rec(pivot_iter + 1, end, depth, comp);
301 template <typename RandomIterator>
302 inline size_t introsort_depth(RandomIterator begin, RandomIterator end)
304 size_t numElems = size_t(end - begin);
307 for (; numElems != 0; numElems >>= 1, ++lg2)
313 } // namespace introsort_detail
315 template <typename RandomIterator, typename Comparator>
316 inline void introsort(RandomIterator begin, RandomIterator end, Comparator comp)
318 introsort_detail::introsort_rec(begin, end, introsort_detail::introsort_depth(begin, end), comp);
320 //introsort_detail::insertion_sort(begin, end, comp);
322 #ifdef VOGL_BUILD_DEBUG
323 // I'm paranoid, there are way too many ways of subtly fucking this up.
326 for (RandomIterator it = begin + 1; it != end; ++it)
327 VOGL_ASSERT(utils::compare_le(*(it - 1), *it, comp));
332 template <typename RandomIterator>
333 inline void introsort(RandomIterator begin, RandomIterator end)
335 introsort(begin, end, std::less<typename std::iterator_traits<RandomIterator>::value_type>());
338 bool introsort_test();
342 #endif // VOGL_INTROSORT_H