This source file includes following definitions.
- merge
- merge_sort_fromto
- merge_sort_inplace
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 static void
45 merge (const ELEMENT *src1, size_t n1,
46 const ELEMENT *src2, size_t n2,
47 ELEMENT *dst)
48 {
49 for (;;)
50 {
51 if (COMPARE (src1, src2) <= 0)
52 {
53 *dst++ = *src1++;
54 n1--;
55 if (n1 == 0)
56 break;
57 }
58 else
59 {
60 *dst++ = *src2++;
61 n2--;
62 if (n2 == 0)
63 break;
64 }
65 }
66
67 if (n1 > 0)
68 {
69 if (dst != src1)
70 do
71 {
72 *dst++ = *src1++;
73 n1--;
74 }
75 while (n1 > 0);
76 }
77 else
78 {
79 if (dst != src2)
80 do
81 {
82 *dst++ = *src2++;
83 n2--;
84 }
85 while (n2 > 0);
86 }
87 }
88
89
90
91
92 #ifdef STATIC_FROMTO
93 STATIC_FROMTO
94 #else
95 STATIC
96 #endif
97 void
98 merge_sort_fromto (const ELEMENT *src, ELEMENT *dst, size_t n, ELEMENT *tmp)
99 {
100 switch (n)
101 {
102 case 0:
103 return;
104 case 1:
105
106 dst[0] = src[0];
107 return;
108 case 2:
109
110 if (COMPARE (&src[0], &src[1]) <= 0)
111 {
112
113 dst[0] = src[0];
114 dst[1] = src[1];
115 }
116 else
117 {
118 dst[0] = src[1];
119 dst[1] = src[0];
120 }
121 break;
122 case 3:
123
124 if (COMPARE (&src[0], &src[1]) <= 0)
125 {
126 if (COMPARE (&src[1], &src[2]) <= 0)
127 {
128
129 dst[0] = src[0];
130 dst[1] = src[1];
131 dst[2] = src[2];
132 }
133 else if (COMPARE (&src[0], &src[2]) <= 0)
134 {
135
136 dst[0] = src[0];
137 dst[1] = src[2];
138 dst[2] = src[1];
139 }
140 else
141 {
142
143 dst[0] = src[2];
144 dst[1] = src[0];
145 dst[2] = src[1];
146 }
147 }
148 else
149 {
150 if (COMPARE (&src[0], &src[2]) <= 0)
151 {
152
153 dst[0] = src[1];
154 dst[1] = src[0];
155 dst[2] = src[2];
156 }
157 else if (COMPARE (&src[1], &src[2]) <= 0)
158 {
159
160 dst[0] = src[1];
161 dst[1] = src[2];
162 dst[2] = src[0];
163 }
164 else
165 {
166
167 dst[0] = src[2];
168 dst[1] = src[1];
169 dst[2] = src[0];
170 }
171 }
172 break;
173 default:
174 {
175 size_t n1 = n / 2;
176 size_t n2 = (n + 1) / 2;
177
178
179 merge_sort_fromto (src + n1, dst + n1, n2, tmp);
180
181 merge_sort_fromto (src, tmp, n1, dst);
182
183 merge (tmp, n1, dst + n1, n2, dst);
184 }
185 break;
186 }
187 }
188
189
190
191 STATIC void
192 merge_sort_inplace (ELEMENT *src, size_t n, ELEMENT *tmp)
193 {
194 switch (n)
195 {
196 case 0:
197 case 1:
198
199 return;
200 case 2:
201
202 if (COMPARE (&src[0], &src[1]) <= 0)
203 {
204
205 }
206 else
207 {
208 ELEMENT t = src[0];
209 src[0] = src[1];
210 src[1] = t;
211 }
212 break;
213 case 3:
214
215 if (COMPARE (&src[0], &src[1]) <= 0)
216 {
217 if (COMPARE (&src[1], &src[2]) <= 0)
218 {
219
220 }
221 else if (COMPARE (&src[0], &src[2]) <= 0)
222 {
223
224 ELEMENT t = src[1];
225 src[1] = src[2];
226 src[2] = t;
227 }
228 else
229 {
230
231 ELEMENT t = src[0];
232 src[0] = src[2];
233 src[2] = src[1];
234 src[1] = t;
235 }
236 }
237 else
238 {
239 if (COMPARE (&src[0], &src[2]) <= 0)
240 {
241
242 ELEMENT t = src[0];
243 src[0] = src[1];
244 src[1] = t;
245 }
246 else if (COMPARE (&src[1], &src[2]) <= 0)
247 {
248
249 ELEMENT t = src[0];
250 src[0] = src[1];
251 src[1] = src[2];
252 src[2] = t;
253 }
254 else
255 {
256
257 ELEMENT t = src[0];
258 src[0] = src[2];
259 src[2] = t;
260 }
261 }
262 break;
263 default:
264 {
265 size_t n1 = n / 2;
266 size_t n2 = (n + 1) / 2;
267
268
269 merge_sort_inplace (src + n1, n2, tmp);
270
271 merge_sort_fromto (src, tmp, n1, tmp + n1);
272
273 merge (tmp, n1, src + n1, n2, src);
274 }
275 break;
276 }
277 }
278
279 #undef ELEMENT
280 #undef COMPARE
281 #undef STATIC