Mercurial > hg > octave-kai > gnulib-hg
annotate lib/array-mergesort.h @ 17463:203c036eb0c6
bootstrap: support checksum utils without a --status option
* build-aux/bootstrap: Only look for sha1sum if updating po files.
Add sha1 to the list of supported checksum utils since it's now
supported through adjustments below.
(update_po_files): Remove the use of --status
in a way that will suppress all error messages, but since this is
only used to minimize updates, it shouldn't cause an issue.
Exit early if there is a problem updating the po file checksums.
(find_tool): Remove the check for --version support as this
is optional as per commit 86186b17. Don't even check for the
presence of the command as if that is needed, it's supported
through configuring prerequisites in bootstrap.conf.
Prompt that when a tool isn't found, one can define an environment
variable to add to the hardcoded search list.
| author | Pádraig Brady <P@draigBrady.com> |
|---|---|
| date | Thu, 08 Aug 2013 11:08:49 +0100 |
| parents | e542fd46ad6f |
| children |
| rev | line source |
|---|---|
| 11167 | 1 /* Stable-sorting of an array using mergesort. |
|
17249
e542fd46ad6f
maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents:
16201
diff
changeset
|
2 Copyright (C) 2009-2013 Free Software Foundation, Inc. |
| 11167 | 3 Written by Bruno Haible <bruno@clisp.org>, 2009. |
| 4 | |
| 5 This program is free software: you can redistribute it and/or modify it | |
| 6 under the terms of the GNU Lesser General Public License as published | |
| 7 by the Free Software Foundation; either version 3 of the License, or | |
| 8 (at your option) any later version. | |
| 9 | |
| 10 This program is distributed in the hope that it will be useful, | |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 Lesser General Public License for more details. | |
| 14 | |
| 15 You should have received a copy of the GNU Lesser General Public License | |
| 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
| 17 | |
| 18 /* This file implements stable sorting of an array, using the mergesort | |
| 19 algorithm. | |
| 20 Worst-case running time for an array of length N is O(N log N). | |
| 21 Unlike the mpsort module, the algorithm here attempts to minimize not | |
| 22 only the number of comparisons, but also the number of copying operations. | |
| 23 | |
| 24 Before including this file, you need to define | |
| 25 ELEMENT The type of every array element. | |
| 26 COMPARE A two-argument macro that takes two 'const ELEMENT *' | |
| 27 pointers and returns a negative, zero, or positive 'int' | |
| 28 value if the element pointed to by the first argument is, | |
| 29 respectively, less, equal, or greater than the element | |
| 30 pointed to by the second argument. | |
| 31 STATIC The storage class of the functions being defined. | |
| 32 Before including this file, you also need to include: | |
| 33 #include <stddef.h> | |
| 34 */ | |
| 35 | |
| 36 /* Merge the sorted arrays src1[0..n1-1] and src2[0..n2-1] into | |
| 37 dst[0..n1+n2-1]. In case of ambiguity, put the elements of src1 | |
| 38 before the elements of src2. | |
| 39 n1 and n2 must be > 0. | |
| 40 The arrays src1 and src2 must not overlap the dst array, except that | |
| 41 src1 may be dst[n2..n1+n2-1], or src2 may be dst[n1..n1+n2-1]. */ | |
| 42 static void | |
| 43 merge (const ELEMENT *src1, size_t n1, | |
| 44 const ELEMENT *src2, size_t n2, | |
| 45 ELEMENT *dst) | |
| 46 { | |
| 47 for (;;) /* while (n1 > 0 && n2 > 0) */ | |
| 48 { | |
| 49 if (COMPARE (src1, src2) <= 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
50 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
51 *dst++ = *src1++; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
52 n1--; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
53 if (n1 == 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
54 break; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
55 } |
| 11167 | 56 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
57 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
58 *dst++ = *src2++; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
59 n2--; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
60 if (n2 == 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
61 break; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
62 } |
| 11167 | 63 } |
| 64 /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0. */ | |
| 65 if (n1 > 0) | |
| 66 { | |
| 67 if (dst != src1) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
68 do |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
69 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
70 *dst++ = *src1++; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
71 n1--; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
72 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
73 while (n1 > 0); |
| 11167 | 74 } |
| 75 else /* n2 > 0 */ | |
| 76 { | |
| 77 if (dst != src2) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
78 do |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
79 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
80 *dst++ = *src2++; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
81 n2--; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
82 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
83 while (n2 > 0); |
| 11167 | 84 } |
| 85 } | |
| 86 | |
| 87 /* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary | |
| 88 (scratch) storage. | |
| 89 The arrays src, dst, tmp must not overlap. */ | |
| 90 STATIC void | |
| 91 merge_sort_fromto (const ELEMENT *src, ELEMENT *dst, size_t n, ELEMENT *tmp) | |
| 92 { | |
| 93 switch (n) | |
| 94 { | |
| 95 case 0: | |
| 96 return; | |
| 97 case 1: | |
| 98 /* Nothing to do. */ | |
| 99 dst[0] = src[0]; | |
| 100 return; | |
| 101 case 2: | |
| 102 /* Trivial case. */ | |
| 103 if (COMPARE (&src[0], &src[1]) <= 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
104 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
105 /* src[0] <= src[1] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
106 dst[0] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
107 dst[1] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
108 } |
| 11167 | 109 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
110 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
111 dst[0] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
112 dst[1] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
113 } |
| 11167 | 114 break; |
| 115 case 3: | |
| 116 /* Simple case. */ | |
| 117 if (COMPARE (&src[0], &src[1]) <= 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
118 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
119 if (COMPARE (&src[1], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
120 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
121 /* src[0] <= src[1] <= src[2] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
122 dst[0] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
123 dst[1] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
124 dst[2] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
125 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
126 else if (COMPARE (&src[0], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
127 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
128 /* src[0] <= src[2] < src[1] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
129 dst[0] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
130 dst[1] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
131 dst[2] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
132 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
133 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
134 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
135 /* src[2] < src[0] <= src[1] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
136 dst[0] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
137 dst[1] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
138 dst[2] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
139 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
140 } |
| 11167 | 141 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
142 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
143 if (COMPARE (&src[0], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
144 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
145 /* src[1] < src[0] <= src[2] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
146 dst[0] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
147 dst[1] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
148 dst[2] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
149 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
150 else if (COMPARE (&src[1], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
151 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
152 /* src[1] <= src[2] < src[0] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
153 dst[0] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
154 dst[1] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
155 dst[2] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
156 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
157 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
158 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
159 /* src[2] < src[1] < src[0] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
160 dst[0] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
161 dst[1] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
162 dst[2] = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
163 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
164 } |
| 11167 | 165 break; |
| 166 default: | |
| 167 { | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
168 size_t n1 = n / 2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
169 size_t n2 = (n + 1) / 2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
170 /* Note: n1 + n2 = n, n1 <= n2. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
171 /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1]. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
172 merge_sort_fromto (src + n1, dst + n1, n2, tmp); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
173 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1]. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
174 merge_sort_fromto (src, tmp, n1, dst); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
175 /* Merge the two half results. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
176 merge (tmp, n1, dst + n1, n2, dst); |
| 11167 | 177 } |
| 178 break; | |
| 179 } | |
| 180 } | |
| 181 | |
| 182 /* Sort src[0..n-1], using tmp[0..n-1] as temporary (scratch) storage. | |
| 183 The arrays src, tmp must not overlap. */ | |
| 184 STATIC void | |
| 185 merge_sort_inplace (ELEMENT *src, size_t n, ELEMENT *tmp) | |
| 186 { | |
| 187 switch (n) | |
| 188 { | |
| 189 case 0: | |
| 190 case 1: | |
| 191 /* Nothing to do. */ | |
| 192 return; | |
| 193 case 2: | |
| 194 /* Trivial case. */ | |
| 195 if (COMPARE (&src[0], &src[1]) <= 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
196 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
197 /* src[0] <= src[1] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
198 } |
| 11167 | 199 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
200 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
201 ELEMENT t = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
202 src[0] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
203 src[1] = t; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
204 } |
| 11167 | 205 break; |
| 206 case 3: | |
| 207 /* Simple case. */ | |
| 208 if (COMPARE (&src[0], &src[1]) <= 0) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
209 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
210 if (COMPARE (&src[1], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
211 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
212 /* src[0] <= src[1] <= src[2] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
213 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
214 else if (COMPARE (&src[0], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
215 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
216 /* src[0] <= src[2] < src[1] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
217 ELEMENT t = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
218 src[1] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
219 src[2] = t; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
220 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
221 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
222 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
223 /* src[2] < src[0] <= src[1] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
224 ELEMENT t = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
225 src[0] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
226 src[2] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
227 src[1] = t; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
228 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
229 } |
| 11167 | 230 else |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
231 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
232 if (COMPARE (&src[0], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
233 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
234 /* src[1] < src[0] <= src[2] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
235 ELEMENT t = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
236 src[0] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
237 src[1] = t; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
238 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
239 else if (COMPARE (&src[1], &src[2]) <= 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
240 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
241 /* src[1] <= src[2] < src[0] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
242 ELEMENT t = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
243 src[0] = src[1]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
244 src[1] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
245 src[2] = t; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
246 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
247 else |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
248 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
249 /* src[2] < src[1] < src[0] */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
250 ELEMENT t = src[0]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
251 src[0] = src[2]; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
252 src[2] = t; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
253 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
254 } |
| 11167 | 255 break; |
| 256 default: | |
| 257 { | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
258 size_t n1 = n / 2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
259 size_t n2 = (n + 1) / 2; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
260 /* Note: n1 + n2 = n, n1 <= n2. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
261 /* Sort src[n1..n-1], scratching tmp[0..n2-1]. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
262 merge_sort_inplace (src + n1, n2, tmp); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
263 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2*n1-1]. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
264 merge_sort_fromto (src, tmp, n1, tmp + n1); |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
265 /* Merge the two half results. */ |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
11167
diff
changeset
|
266 merge (tmp, n1, src + n1, n2, src); |
| 11167 | 267 } |
| 268 break; | |
| 269 } | |
| 270 } | |
| 271 | |
| 272 #undef ELEMENT | |
| 273 #undef COMPARE | |
| 274 #undef STATIC |