lib/array-mergesort.h

   1 /* Stable-sorting of an array using mergesort.
   2    Copyright (C) 2009-2017 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].  */
  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)
  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.  */
  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)
 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. */
 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)
 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