/* Sort a vector of pointers to data.

   Copyright (C) 2007, 2009-2018 Free Software Foundation, Inc.

   This program is free software: you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 3 of the License, or

   (at your option) any later version.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

/* Written by Paul Eggert.  */

#include <config.h>

#include "mpsort.h"

#include <string.h>

/* The type of qsort-style comparison functions.  */

typedef int (*comparison_function) (void const *, void const *);

static void mpsort_with_tmp (void const **restrict, size_t,

                             void const **restrict, comparison_function);

/* Sort a vector BASE containing N pointers, placing the sorted array

   into TMP.  Compare pointers with CMP.  N must be at least 2.  */

static void

mpsort_into_tmp (void const **restrict base, size_t n,

                 void const **restrict tmp,

                 comparison_function cmp)

{

  size_t n1 = n / 2;

  size_t n2 = n - n1;

  size_t a = 0;

  size_t alim = n1;

  size_t b = n1;

  size_t blim = n;

  void const *ba;

  void const *bb;

  mpsort_with_tmp (base + n1, n2, tmp, cmp);

  mpsort_with_tmp (base, n1, tmp, cmp);

  ba = base[a];

  bb = base[b];

  for (;;)

    if (cmp (ba, bb) <= 0)

      {

        *tmp++ = ba;

        a++;

        if (a == alim)

          {

            a = b;

            alim = blim;

            break;

          }

        ba = base[a];

      }

    else

      {

        *tmp++ = bb;

        b++;

        if (b == blim)

          break;

        bb = base[b];

      }

  memcpy (tmp, base + a, (alim - a) * sizeof *base);

}

/* Sort a vector BASE containing N pointers, in place.  Use TMP

   (containing N / 2 pointers) for temporary storage.  Compare

   pointers with CMP.  */

static void

mpsort_with_tmp (void const **restrict base, size_t n,

                 void const **restrict tmp,

                 comparison_function cmp)

{

  if (n <= 2)

    {

      if (n == 2)

        {

          void const *p0 = base[0];

          void const *p1 = base[1];

          if (! (cmp (p0, p1) <= 0))

            {

              base[0] = p1;

              base[1] = p0;

            }

        }

    }

  else

    {

      size_t n1 = n / 2;

      size_t n2 = n - n1;

      size_t i;

      size_t t = 0;

      size_t tlim = n1;

      size_t b = n1;

      size_t blim = n;

      void const *bb;

      void const *tt;

      mpsort_with_tmp (base + n1, n2, tmp, cmp);

      if (n1 < 2)

        tmp[0] = base[0];

      else

        mpsort_into_tmp (base, n1, tmp, cmp);

      tt = tmp[t];

      bb = base[b];

      for (i = 0; ; )

        if (cmp (tt, bb) <= 0)

          {

            base[i++] = tt;

            t++;

            if (t == tlim)

              break;

            tt = tmp[t];

          }

        else

          {

            base[i++] = bb;

            b++;

            if (b == blim)

              {

                memcpy (base + i, tmp + t, (tlim - t) * sizeof *base);

                break;

              }

            bb = base[b];

          }

    }

}

/* Sort a vector BASE containing N pointers, in place.  BASE must

   contain enough storage to hold N + N / 2 vectors; the trailing

   vectors are used for temporaries.  Compare pointers with CMP.  */

void

mpsort (void const **base, size_t n, comparison_function cmp)

{

  mpsort_with_tmp (base, n, base + n, cmp);

}