Mercurial > hg > octave-kai > gnulib-hg

comparison lib/array-mergesort.h @ 12421:e8d2c6fc33ad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Use spaces for indentation, not tabs.
author Bruno Haible <bruno@clisp.org>
date Thu, 10 Dec 2009 20:28:30 +0100
parents d11190b43f68
children c2cbabec01dd
comparison
equal deleted inserted replaced
12420:5850b9a81029 12421:e8d2c6fc33ad
45 ELEMENT *dst) 45 ELEMENT *dst)
46 { 46 {
47 for (;;) /* while (n1 > 0 && n2 > 0) */ 47 for (;;) /* while (n1 > 0 && n2 > 0) */
48 { 48 {
49 if (COMPARE (src1, src2) <= 0) 49 if (COMPARE (src1, src2) <= 0)
50 { 50 {
51 *dst++ = *src1++; 51 *dst++ = *src1++;
52 n1--; 52 n1--;
53 if (n1 == 0) 53 if (n1 == 0)
54 break; 54 break;
55 } 55 }
56 else 56 else
57 { 57 {
58 *dst++ = *src2++; 58 *dst++ = *src2++;
59 n2--; 59 n2--;
60 if (n2 == 0) 60 if (n2 == 0)
61 break; 61 break;
62 } 62 }
63 } 63 }
64 /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0. */ 64 /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0. */
65 if (n1 > 0) 65 if (n1 > 0)
66 { 66 {
67 if (dst != src1) 67 if (dst != src1)
68 do 68 do
69 { 69 {
70 *dst++ = *src1++; 70 *dst++ = *src1++;
71 n1--; 71 n1--;
72 } 72 }
73 while (n1 > 0); 73 while (n1 > 0);
74 } 74 }
75 else /* n2 > 0 */ 75 else /* n2 > 0 */
76 { 76 {
77 if (dst != src2) 77 if (dst != src2)
78 do 78 do
79 { 79 {
80 *dst++ = *src2++; 80 *dst++ = *src2++;
81 n2--; 81 n2--;
82 } 82 }
83 while (n2 > 0); 83 while (n2 > 0);
84 } 84 }
85 } 85 }
86 86
87 /* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary 87 /* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary
88 (scratch) storage. 88 (scratch) storage.
99 dst[0] = src[0]; 99 dst[0] = src[0];
100 return; 100 return;
101 case 2: 101 case 2:
102 /* Trivial case. */ 102 /* Trivial case. */
103 if (COMPARE (&src[0], &src[1]) <= 0) 103 if (COMPARE (&src[0], &src[1]) <= 0)
104 { 104 {
105 /* src[0] <= src[1] */ 105 /* src[0] <= src[1] */
106 dst[0] = src[0]; 106 dst[0] = src[0];
107 dst[1] = src[1]; 107 dst[1] = src[1];
108 } 108 }
109 else 109 else
110 { 110 {
111 dst[0] = src[1]; 111 dst[0] = src[1];
112 dst[1] = src[0]; 112 dst[1] = src[0];
113 } 113 }
114 break; 114 break;
115 case 3: 115 case 3:
116 /* Simple case. */ 116 /* Simple case. */
117 if (COMPARE (&src[0], &src[1]) <= 0) 117 if (COMPARE (&src[0], &src[1]) <= 0)
118 { 118 {
119 if (COMPARE (&src[1], &src[2]) <= 0) 119 if (COMPARE (&src[1], &src[2]) <= 0)
120 { 120 {
121 /* src[0] <= src[1] <= src[2] */ 121 /* src[0] <= src[1] <= src[2] */
122 dst[0] = src[0]; 122 dst[0] = src[0];
123 dst[1] = src[1]; 123 dst[1] = src[1];
124 dst[2] = src[2]; 124 dst[2] = src[2];
125 } 125 }
126 else if (COMPARE (&src[0], &src[2]) <= 0) 126 else if (COMPARE (&src[0], &src[2]) <= 0)
127 { 127 {
128 /* src[0] <= src[2] < src[1] */ 128 /* src[0] <= src[2] < src[1] */
129 dst[0] = src[0]; 129 dst[0] = src[0];
130 dst[1] = src[2]; 130 dst[1] = src[2];
131 dst[2] = src[1]; 131 dst[2] = src[1];
132 } 132 }
133 else 133 else
134 { 134 {
135 /* src[2] < src[0] <= src[1] */ 135 /* src[2] < src[0] <= src[1] */
136 dst[0] = src[2]; 136 dst[0] = src[2];
137 dst[1] = src[0]; 137 dst[1] = src[0];
138 dst[2] = src[1]; 138 dst[2] = src[1];
139 } 139 }
140 } 140 }
141 else 141 else
142 { 142 {
143 if (COMPARE (&src[0], &src[2]) <= 0) 143 if (COMPARE (&src[0], &src[2]) <= 0)
144 { 144 {
145 /* src[1] < src[0] <= src[2] */ 145 /* src[1] < src[0] <= src[2] */
146 dst[0] = src[1]; 146 dst[0] = src[1];
147 dst[1] = src[0]; 147 dst[1] = src[0];
148 dst[2] = src[2]; 148 dst[2] = src[2];
149 } 149 }
150 else if (COMPARE (&src[1], &src[2]) <= 0) 150 else if (COMPARE (&src[1], &src[2]) <= 0)
151 { 151 {
152 /* src[1] <= src[2] < src[0] */ 152 /* src[1] <= src[2] < src[0] */
153 dst[0] = src[1]; 153 dst[0] = src[1];
154 dst[1] = src[2]; 154 dst[1] = src[2];
155 dst[2] = src[0]; 155 dst[2] = src[0];
156 } 156 }
157 else 157 else
158 { 158 {
159 /* src[2] < src[1] < src[0] */ 159 /* src[2] < src[1] < src[0] */
160 dst[0] = src[2]; 160 dst[0] = src[2];
161 dst[1] = src[1]; 161 dst[1] = src[1];
162 dst[2] = src[0]; 162 dst[2] = src[0];
163 } 163 }
164 } 164 }
165 break; 165 break;
166 default: 166 default:
167 { 167 {
168 size_t n1 = n / 2; 168 size_t n1 = n / 2;
169 size_t n2 = (n + 1) / 2; 169 size_t n2 = (n + 1) / 2;
170 /* Note: n1 + n2 = n, n1 <= n2. */ 170 /* Note: n1 + n2 = n, n1 <= n2. */
171 /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1]. */ 171 /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1]. */
172 merge_sort_fromto (src + n1, dst + n1, n2, tmp); 172 merge_sort_fromto (src + n1, dst + n1, n2, tmp);
173 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1]. */ 173 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1]. */
174 merge_sort_fromto (src, tmp, n1, dst); 174 merge_sort_fromto (src, tmp, n1, dst);
175 /* Merge the two half results. */ 175 /* Merge the two half results. */
176 merge (tmp, n1, dst + n1, n2, dst); 176 merge (tmp, n1, dst + n1, n2, dst);
177 } 177 }
178 break; 178 break;
179 } 179 }
180 } 180 }
181 181
191 /* Nothing to do. */ 191 /* Nothing to do. */
192 return; 192 return;
193 case 2: 193 case 2:
194 /* Trivial case. */ 194 /* Trivial case. */
195 if (COMPARE (&src[0], &src[1]) <= 0) 195 if (COMPARE (&src[0], &src[1]) <= 0)
196 { 196 {
197 /* src[0] <= src[1] */ 197 /* src[0] <= src[1] */
198 } 198 }
199 else 199 else
200 { 200 {
201 ELEMENT t = src[0]; 201 ELEMENT t = src[0];
202 src[0] = src[1]; 202 src[0] = src[1];
203 src[1] = t; 203 src[1] = t;
204 } 204 }
205 break; 205 break;
206 case 3: 206 case 3:
207 /* Simple case. */ 207 /* Simple case. */
208 if (COMPARE (&src[0], &src[1]) <= 0) 208 if (COMPARE (&src[0], &src[1]) <= 0)
209 { 209 {
210 if (COMPARE (&src[1], &src[2]) <= 0) 210 if (COMPARE (&src[1], &src[2]) <= 0)
211 { 211 {
212 /* src[0] <= src[1] <= src[2] */ 212 /* src[0] <= src[1] <= src[2] */
213 } 213 }
214 else if (COMPARE (&src[0], &src[2]) <= 0) 214 else if (COMPARE (&src[0], &src[2]) <= 0)
215 { 215 {
216 /* src[0] <= src[2] < src[1] */ 216 /* src[0] <= src[2] < src[1] */
217 ELEMENT t = src[1]; 217 ELEMENT t = src[1];
218 src[1] = src[2]; 218 src[1] = src[2];
219 src[2] = t; 219 src[2] = t;
220 } 220 }
221 else 221 else
222 { 222 {
223 /* src[2] < src[0] <= src[1] */ 223 /* src[2] < src[0] <= src[1] */
224 ELEMENT t = src[0]; 224 ELEMENT t = src[0];
225 src[0] = src[2]; 225 src[0] = src[2];
226 src[2] = src[1]; 226 src[2] = src[1];
227 src[1] = t; 227 src[1] = t;
228 } 228 }
229 } 229 }
230 else 230 else
231 { 231 {
232 if (COMPARE (&src[0], &src[2]) <= 0) 232 if (COMPARE (&src[0], &src[2]) <= 0)
233 { 233 {
234 /* src[1] < src[0] <= src[2] */ 234 /* src[1] < src[0] <= src[2] */
235 ELEMENT t = src[0]; 235 ELEMENT t = src[0];
236 src[0] = src[1]; 236 src[0] = src[1];
237 src[1] = t; 237 src[1] = t;
238 } 238 }
239 else if (COMPARE (&src[1], &src[2]) <= 0) 239 else if (COMPARE (&src[1], &src[2]) <= 0)
240 { 240 {
241 /* src[1] <= src[2] < src[0] */ 241 /* src[1] <= src[2] < src[0] */
242 ELEMENT t = src[0]; 242 ELEMENT t = src[0];
243 src[0] = src[1]; 243 src[0] = src[1];
244 src[1] = src[2]; 244 src[1] = src[2];
245 src[2] = t; 245 src[2] = t;
246 } 246 }
247 else 247 else
248 { 248 {
249 /* src[2] < src[1] < src[0] */ 249 /* src[2] < src[1] < src[0] */
250 ELEMENT t = src[0]; 250 ELEMENT t = src[0];
251 src[0] = src[2]; 251 src[0] = src[2];
252 src[2] = t; 252 src[2] = t;
253 } 253 }
254 } 254 }
255 break; 255 break;
256 default: 256 default:
257 { 257 {
258 size_t n1 = n / 2; 258 size_t n1 = n / 2;
259 size_t n2 = (n + 1) / 2; 259 size_t n2 = (n + 1) / 2;
260 /* Note: n1 + n2 = n, n1 <= n2. */ 260 /* Note: n1 + n2 = n, n1 <= n2. */
261 /* Sort src[n1..n-1], scratching tmp[0..n2-1]. */ 261 /* Sort src[n1..n-1], scratching tmp[0..n2-1]. */
262 merge_sort_inplace (src + n1, n2, tmp); 262 merge_sort_inplace (src + n1, n2, tmp);
263 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2*n1-1]. */ 263 /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2*n1-1]. */
264 merge_sort_fromto (src, tmp, n1, tmp + n1); 264 merge_sort_fromto (src, tmp, n1, tmp + n1);
265 /* Merge the two half results. */ 265 /* Merge the two half results. */
266 merge (tmp, n1, src + n1, n2, src); 266 merge (tmp, n1, src + n1, n2, src);
267 } 267 }
268 break; 268 break;
269 } 269 }
270 } 270 }
271 271