lib/array-mergesort.h

   1 /* Stable-sorting of an array using mergesort.
   2    Copyright (C) 2009-2020 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 <https://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      STATIC_FROMTO  (Optional.) Overrides STATIC for the 'merge_sort_fromto'
  33                     function.
  34    Before including this file, you also need to include:
  35      #include <stddef.h>
  36  */
  37
  38 /* Merge the sorted arrays src1[0..n1-1] and src2[0..n2-1] into
  39    dst[0..n1+n2-1].  In case of ambiguity, put the elements of src1
  40    before the elements of src2.
  41    n1 and n2 must be > 0.
  42    The arrays src1 and src2 must not overlap the dst array, except that
  43    src1 may be dst[n2..n1+n2-1], or src2 may be dst[n1..n1+n2-1].  */
  44 static void
  45 merge (const ELEMENT *src1, size_t n1,
  46        const ELEMENT *src2, size_t n2,
  47        ELEMENT *dst)
  48 {
  49   for (;;) /* while (n1 > 0 && n2 > 0) */
  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   /* Here n1 == 0 || n2 == 0 but also n1 > 0 || n2 > 0.  */
  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 /* n2 > 0 */
  78     {
  79       if (dst != src2)
  80         do
  81           {
  82             *dst++ = *src2++;
  83             n2--;
  84           }
  85         while (n2 > 0);
  86     }
  87 }
  88
  89 /* Sort src[0..n-1] into dst[0..n-1], using tmp[0..n/2-1] as temporary
  90    (scratch) storage.
  91    The arrays src, dst, tmp must not overlap.  */
  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       /* Nothing to do.  */
 106       dst[0] = src[0];
 107       return;
 108     case 2:
 109       /* Trivial case.  */
 110       if (COMPARE (&src[0], &src[1]) <= 0)
 111         {
 112           /* src[0] <= src[1] */
 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       /* Simple case.  */
 124       if (COMPARE (&src[0], &src[1]) <= 0)
 125         {
 126           if (COMPARE (&src[1], &src[2]) <= 0)
 127             {
 128               /* src[0] <= src[1] <= src[2] */
 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               /* src[0] <= src[2] < src[1] */
 136               dst[0] = src[0];
 137               dst[1] = src[2];
 138               dst[2] = src[1];
 139             }
 140           else
 141             {
 142               /* src[2] < src[0] <= src[1] */
 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               /* src[1] < src[0] <= src[2] */
 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               /* src[1] <= src[2] < src[0] */
 160               dst[0] = src[1];
 161               dst[1] = src[2];
 162               dst[2] = src[0];
 163             }
 164           else
 165             {
 166               /* src[2] < src[1] < src[0] */
 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         /* Note: n1 + n2 = n, n1 <= n2.  */
 178         /* Sort src[n1..n-1] into dst[n1..n-1], scratching tmp[0..n2/2-1].  */
 179         merge_sort_fromto (src + n1, dst + n1, n2, tmp);
 180         /* Sort src[0..n1-1] into tmp[0..n1-1], scratching dst[0..n1-1].  */
 181         merge_sort_fromto (src, tmp, n1, dst);
 182         /* Merge the two half results.  */
 183         merge (tmp, n1, dst + n1, n2, dst);
 184       }
 185       break;
 186     }
 187 }
 188
 189 /* Sort src[0..n-1], using tmp[0..n-1] as temporary (scratch) storage.
 190    The arrays src, tmp must not overlap. */
 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       /* Nothing to do.  */
 199       return;
 200     case 2:
 201       /* Trivial case.  */
 202       if (COMPARE (&src[0], &src[1]) <= 0)
 203         {
 204           /* src[0] <= src[1] */
 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       /* Simple case.  */
 215       if (COMPARE (&src[0], &src[1]) <= 0)
 216         {
 217           if (COMPARE (&src[1], &src[2]) <= 0)
 218             {
 219               /* src[0] <= src[1] <= src[2] */
 220             }
 221           else if (COMPARE (&src[0], &src[2]) <= 0)
 222             {
 223               /* src[0] <= src[2] < src[1] */
 224               ELEMENT t = src[1];
 225               src[1] = src[2];
 226               src[2] = t;
 227             }
 228           else
 229             {
 230               /* src[2] < src[0] <= src[1] */
 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               /* src[1] < src[0] <= src[2] */
 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               /* src[1] <= src[2] < src[0] */
 249               ELEMENT t = src[0];
 250               src[0] = src[1];
 251               src[1] = src[2];
 252               src[2] = t;
 253             }
 254           else
 255             {
 256               /* src[2] < src[1] < src[0] */
 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         /* Note: n1 + n2 = n, n1 <= n2.  */
 268         /* Sort src[n1..n-1], scratching tmp[0..n2-1].  */
 269         merge_sort_inplace (src + n1, n2, tmp);
 270         /* Sort src[0..n1-1] into tmp[0..n1-1], scratching tmp[n1..2*n1-1].  */
 271         merge_sort_fromto (src, tmp, n1, tmp + n1);
 272         /* Merge the two half results.  */
 273         merge (tmp, n1, src + n1, n2, src);
 274       }
 275       break;
 276     }
 277 }
 278
 279 #undef ELEMENT
 280 #undef COMPARE
 281 #undef STATIC