1 /* Stable-sorting of an array using mergesort.
2 Copyright (C) 2009-2018 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2009.
4
5 This program is free software: you can redistribute it and/or
6 modify it under the terms of either:
7
8 * the GNU Lesser General Public License as published by the Free
9 Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 or
13
14 * the GNU General Public License as published by the Free
15 Software Foundation; either version 2 of the License, or (at your
16 option) any later version.
17
18 or both in parallel, as here.
19 This program is distributed in the hope that it will be useful,
20 but WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 Lesser General Public License for more details.
23
24 You should have received a copy of the GNU Lesser General Public License
25 along with this program. If not, see <https://www.gnu.org/licenses/>. */
26
27 /* This file implements stable sorting of an array, using the mergesort
28 algorithm.
29 Worst-case running time for an array of length N is O(N log N).
30 Unlike the mpsort module, the algorithm here attempts to minimize not
31 only the number of comparisons, but also the number of copying operations.
32
33 Before including this file, you need to define
34 ELEMENT The type of every array element.
35 COMPARE A two-argument macro that takes two 'const ELEMENT *'
36 pointers and returns a negative, zero, or positive 'int'
37 value if the element pointed to by the first argument is,
38 respectively, less, equal, or greater than the element
39 pointed to by the second argument.
40 STATIC The storage class of the functions being defined.
41 Before including this file, you also need to include:
42 #include <stddef.h>
43 */
44
45 /* Merge the sorted arrays src1[0..n1-1] and src2[0..n2-1] into
46 dst[0..n1+n2-1]. In case of ambiguity, put the elements of src1
47 before the elements of src2.
48 n1 and n2 must be > 0.
49 The arrays src1 and src2 must not overlap the dst array, except that
50 src1 may be dst[n2..n1+n2-1], or src2 may be dst[n1..n1+n2-1]. */
51 static void
merge(const ELEMENT * src1,size_t n1,const ELEMENT * src2,size_t n2,ELEMENT * dst)52 merge (const ELEMENT *src1, size_t n1,
53 const ELEMENT *src2, size_t n2,
54 ELEMENT *dst)
55 {
56 for (;;) /* while (n1 > 0 && n2 > 0) */
57 {
58 if (COMPARE (src1, src2) <= 0)
59 {
60 *dst++ = *src1++;
61 n1--;
62 if (n1 == 0)
63 break;
64 }
65 else
66 {
67 *dst++ = *src2++;
68 n2--;
69 if (n2 == 0)
70 break;
71 }
72 }
73 /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0. */
74 if (n1 > 0)
75 {
76 if (dst != src1)
77 do
78 {
79 *dst++ = *src1++;
80 n1--;
81 }
82 while (n1 > 0);
83 }
84 else /* n2 > 0 */
85 {
86 if (dst != src2)
87 do
88 {
89 *dst++ = *src2++;
90 n2--;
91 }
92 while (n2 > 0);
93 }
94 }
95
96 /* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary
97 (scratch) storage.
98 The arrays src, dst, tmp must not overlap. */
99 STATIC void
merge_sort_fromto(const ELEMENT * src,ELEMENT * dst,size_t n,ELEMENT * tmp)100 merge_sort_fromto (const ELEMENT *src, ELEMENT *dst, size_t n, ELEMENT *tmp)
101 {
102 switch (n)
103 {
104 case 0:
105 return;
106 case 1:
107 /* Nothing to do. */
108 dst[0] = src[0];
109 return;
110 case 2:
111 /* Trivial case. */
112 if (COMPARE (&src[0], &src[1]) <= 0)
113 {
114 /* src[0] <= src[1] */
115 dst[0] = src[0];
116 dst[1] = src[1];
117 }
118 else
119 {
120 dst[0] = src[1];
121 dst[1] = src[0];
122 }
123 break;
124 case 3:
125 /* Simple case. */
126 if (COMPARE (&src[0], &src[1]) <= 0)
127 {
128 if (COMPARE (&src[1], &src[2]) <= 0)
129 {
130 /* src[0] <= src[1] <= src[2] */
131 dst[0] = src[0];
132 dst[1] = src[1];
133 dst[2] = src[2];
134 }
135 else if (COMPARE (&src[0], &src[2]) <= 0)
136 {
137 /* src[0] <= src[2] < src[1] */
138 dst[0] = src[0];
139 dst[1] = src[2];
140 dst[2] = src[1];
141 }
142 else
143 {
144 /* src[2] < src[0] <= src[1] */
145 dst[0] = src[2];
146 dst[1] = src[0];
147 dst[2] = src[1];
148 }
149 }
150 else
151 {
152 if (COMPARE (&src[0], &src[2]) <= 0)
153 {
154 /* src[1] < src[0] <= src[2] */
155 dst[0] = src[1];
156 dst[1] = src[0];
157 dst[2] = src[2];
158 }
159 else if (COMPARE (&src[1], &src[2]) <= 0)
160 {
161 /* src[1] <= src[2] < src[0] */
162 dst[0] = src[1];
163 dst[1] = src[2];
164 dst[2] = src[0];
165 }
166 else
167 {
168 /* src[2] < src[1] < src[0] */
169 dst[0] = src[2];
170 dst[1] = src[1];
171 dst[2] = src[0];
172 }
173 }
174 break;
175 default:
176 {
177 size_t n1 = n / 2;
178 size_t n2 = (n + 1) / 2;
179 /* Note: n1 + n2 = n, n1 <= n2. */
180 /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1]. */
181 merge_sort_fromto (src + n1, dst + n1, n2, tmp);
182 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1]. */
183 merge_sort_fromto (src, tmp, n1, dst);
184 /* Merge the two half results. */
185 merge (tmp, n1, dst + n1, n2, dst);
186 }
187 break;
188 }
189 }
190
191 /* Sort src[0..n-1], using tmp[0..n-1] as temporary (scratch) storage.
192 The arrays src, tmp must not overlap. */
193 STATIC void
merge_sort_inplace(ELEMENT * src,size_t n,ELEMENT * tmp)194 merge_sort_inplace (ELEMENT *src, size_t n, ELEMENT *tmp)
195 {
196 switch (n)
197 {
198 case 0:
199 case 1:
200 /* Nothing to do. */
201 return;
202 case 2:
203 /* Trivial case. */
204 if (COMPARE (&src[0], &src[1]) <= 0)
205 {
206 /* src[0] <= src[1] */
207 }
208 else
209 {
210 ELEMENT t = src[0];
211 src[0] = src[1];
212 src[1] = t;
213 }
214 break;
215 case 3:
216 /* Simple case. */
217 if (COMPARE (&src[0], &src[1]) <= 0)
218 {
219 if (COMPARE (&src[1], &src[2]) <= 0)
220 {
221 /* src[0] <= src[1] <= src[2] */
222 }
223 else if (COMPARE (&src[0], &src[2]) <= 0)
224 {
225 /* src[0] <= src[2] < src[1] */
226 ELEMENT t = src[1];
227 src[1] = src[2];
228 src[2] = t;
229 }
230 else
231 {
232 /* src[2] < src[0] <= src[1] */
233 ELEMENT t = src[0];
234 src[0] = src[2];
235 src[2] = src[1];
236 src[1] = t;
237 }
238 }
239 else
240 {
241 if (COMPARE (&src[0], &src[2]) <= 0)
242 {
243 /* src[1] < src[0] <= src[2] */
244 ELEMENT t = src[0];
245 src[0] = src[1];
246 src[1] = t;
247 }
248 else if (COMPARE (&src[1], &src[2]) <= 0)
249 {
250 /* src[1] <= src[2] < src[0] */
251 ELEMENT t = src[0];
252 src[0] = src[1];
253 src[1] = src[2];
254 src[2] = t;
255 }
256 else
257 {
258 /* src[2] < src[1] < src[0] */
259 ELEMENT t = src[0];
260 src[0] = src[2];
261 src[2] = t;
262 }
263 }
264 break;
265 default:
266 {
267 size_t n1 = n / 2;
268 size_t n2 = (n + 1) / 2;
269 /* Note: n1 + n2 = n, n1 <= n2. */
270 /* Sort src[n1..n-1], scratching tmp[0..n2-1]. */
271 merge_sort_inplace (src + n1, n2, tmp);
272 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2*n1-1]. */
273 merge_sort_fromto (src, tmp, n1, tmp + n1);
274 /* Merge the two half results. */
275 merge (tmp, n1, src + n1, n2, src);
276 }
277 break;
278 }
279 }
280
281 #undef ELEMENT
282 #undef COMPARE
283 #undef STATIC
284