1/* Stable-sorting of an array using mergesort.
2   Copyright (C) 2009, 2010 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 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].  */
42static void
43merge (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)
50        {
51          *dst++ = *src1++;
52          n1--;
53          if (n1 == 0)
54            break;
55        }
56      else
57        {
58          *dst++ = *src2++;
59          n2--;
60          if (n2 == 0)
61            break;
62        }
63    }
64  /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0.  */
65  if (n1 > 0)
66    {
67      if (dst != src1)
68        do
69          {
70            *dst++ = *src1++;
71            n1--;
72          }
73        while (n1 > 0);
74    }
75  else /* n2 > 0 */
76    {
77      if (dst != src2)
78        do
79          {
80            *dst++ = *src2++;
81            n2--;
82          }
83        while (n2 > 0);
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.  */
90STATIC void
91merge_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)
104        {
105          /* src[0] <= src[1] */
106          dst[0] = src[0];
107          dst[1] = src[1];
108        }
109      else
110        {
111          dst[0] = src[1];
112          dst[1] = src[0];
113        }
114      break;
115    case 3:
116      /* Simple case.  */
117      if (COMPARE (&src[0], &src[1]) <= 0)
118        {
119          if (COMPARE (&src[1], &src[2]) <= 0)
120            {
121              /* src[0] <= src[1] <= src[2] */
122              dst[0] = src[0];
123              dst[1] = src[1];
124              dst[2] = src[2];
125            }
126          else if (COMPARE (&src[0], &src[2]) <= 0)
127            {
128              /* src[0] <= src[2] < src[1] */
129              dst[0] = src[0];
130              dst[1] = src[2];
131              dst[2] = src[1];
132            }
133          else
134            {
135              /* src[2] < src[0] <= src[1] */
136              dst[0] = src[2];
137              dst[1] = src[0];
138              dst[2] = src[1];
139            }
140        }
141      else
142        {
143          if (COMPARE (&src[0], &src[2]) <= 0)
144            {
145              /* src[1] < src[0] <= src[2] */
146              dst[0] = src[1];
147              dst[1] = src[0];
148              dst[2] = src[2];
149            }
150          else if (COMPARE (&src[1], &src[2]) <= 0)
151            {
152              /* src[1] <= src[2] < src[0] */
153              dst[0] = src[1];
154              dst[1] = src[2];
155              dst[2] = src[0];
156            }
157          else
158            {
159              /* src[2] < src[1] < src[0] */
160              dst[0] = src[2];
161              dst[1] = src[1];
162              dst[2] = src[0];
163            }
164        }
165      break;
166    default:
167      {
168        size_t n1 = n / 2;
169        size_t n2 = (n + 1) / 2;
170        /* Note: n1 + n2 = n, n1 <= n2.  */
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);
173        /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1].  */
174        merge_sort_fromto (src, tmp, n1, dst);
175        /* Merge the two half results.  */
176        merge (tmp, n1, dst + n1, n2, dst);
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. */
184STATIC void
185merge_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)
196        {
197          /* src[0] <= src[1] */
198        }
199      else
200        {
201          ELEMENT t = src[0];
202          src[0] = src[1];
203          src[1] = t;
204        }
205      break;
206    case 3:
207      /* Simple case.  */
208      if (COMPARE (&src[0], &src[1]) <= 0)
209        {
210          if (COMPARE (&src[1], &src[2]) <= 0)
211            {
212              /* src[0] <= src[1] <= src[2] */
213            }
214          else if (COMPARE (&src[0], &src[2]) <= 0)
215            {
216              /* src[0] <= src[2] < src[1] */
217              ELEMENT t = src[1];
218              src[1] = src[2];
219              src[2] = t;
220            }
221          else
222            {
223              /* src[2] < src[0] <= src[1] */
224              ELEMENT t = src[0];
225              src[0] = src[2];
226              src[2] = src[1];
227              src[1] = t;
228            }
229        }
230      else
231        {
232          if (COMPARE (&src[0], &src[2]) <= 0)
233            {
234              /* src[1] < src[0] <= src[2] */
235              ELEMENT t = src[0];
236              src[0] = src[1];
237              src[1] = t;
238            }
239          else if (COMPARE (&src[1], &src[2]) <= 0)
240            {
241              /* src[1] <= src[2] < src[0] */
242              ELEMENT t = src[0];
243              src[0] = src[1];
244              src[1] = src[2];
245              src[2] = t;
246            }
247          else
248            {
249              /* src[2] < src[1] < src[0] */
250              ELEMENT t = src[0];
251              src[0] = src[2];
252              src[2] = t;
253            }
254        }
255      break;
256    default:
257      {
258        size_t n1 = n / 2;
259        size_t n2 = (n + 1) / 2;
260        /* Note: n1 + n2 = n, n1 <= n2.  */
261        /* Sort src[n1..n-1], scratching tmp[0..n2-1].  */
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].  */
264        merge_sort_fromto (src, tmp, n1, tmp + n1);
265        /* Merge the two half results.  */
266        merge (tmp, n1, src + n1, n2, src);
267      }
268      break;
269    }
270}
271
272#undef ELEMENT
273#undef COMPARE
274#undef STATIC
275