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_mergesort.h
28 // This isn't very fast, and requires extra storage, but it's a reasonably fast stable sort with no degenerate cases.
29 #ifndef VOGL_MERGESORT_H
30 #define VOGL_MERGESORT_H
32 #include "vogl_core.h"
37 struct mergesort_use_swaps_during_merge
45 #define VOGL_MERGESORT_USE_SWAPS_DURING_MERGE(T) \
46 template <> struct mergesort_use_swaps_during_merge<T> \
48 enum { cFlag = true }; \
51 VOGL_MERGESORT_USE_SWAPS_DURING_MERGE(dynamic_string);
56 template <typename T, typename Comparator>
57 inline void BottomUpMerge(vogl::vector<T> &A, uint iLeft, uint iRight, uint iEnd, vogl::vector<T> &B, Comparator comp)
63 /* While there are elements in the left or right lists */
64 for (uint j = iLeft; j < iEnd; j++)
66 /* If left list head exists and is <= existing right list head */
67 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
81 if ((i0 < iRight) && (i1 < iEnd))
85 if (!comp(A[i1], A[i0]))
104 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
112 template <typename T, typename Comparator>
113 inline void BottomUpMergeSwap(vogl::vector<T> &A, uint iLeft, uint iRight, uint iEnd, vogl::vector<T> &B, Comparator comp)
119 /* While there are elements in the left or right lists */
120 for (uint j = iLeft; j < iEnd; j++)
122 /* If left list head exists and is <= existing right list head */
123 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
137 if ((i0 < iRight) && (i1 < iEnd))
141 if (!comp(A[i1], A[i0]))
143 std::swap(B[j++], A[i0++]);
149 std::swap(B[j++], A[i1++]);
160 if ((i0 < iRight) && ((i1 >= iEnd) || (!comp(A[i1], A[i0]))))
161 std::swap(B[j++], A[i0++]);
163 std::swap(B[j++], A[i1++]);
168 /* array A[] has the items to sort; array B[] is a work array */
169 template <typename T, typename Comparator>
170 inline void BottomUpSort(vogl::vector<T> &A, Comparator comp)
172 const uint n = A.size();
174 vogl::vector<T> B(n);
176 /* Each 1-element run in A is already "sorted". */
178 /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted. */
179 for (uint width = 1; width < n; width = 2 * width)
181 /* Array A is full of runs of length width. */
182 for (uint i = 0; i < n; i = i + 2 * width)
184 /* Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
185 /* or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
186 if (mergesort_use_swaps_during_merge<T>::cFlag)
187 BottomUpMergeSwap(A, i, math::minimum(i + width, n), math::minimum(i + 2 * width, n), B, comp);
189 BottomUpMerge(A, i, math::minimum(i + width, n), math::minimum(i + 2 * width, n), B, comp);
192 /* Now work array B is full of runs of length 2*width. */
193 /* Swap array B to array A for next iteration. */
195 /* Now array A is full of runs of length 2*width. */
199 } // namespace detail
201 template <typename T, typename Comparator>
202 inline void mergesort(vogl::vector<T> &elems, Comparator comp)
204 detail::BottomUpSort(elems, comp);
207 template <typename T>
208 inline void mergesort(vogl::vector<T> &elems)
210 mergesort(elems, std::less<T>());
215 #endif // VOGL_MERGESORT_H