sortC()

template<typename Sorter>

void QuickSorter< Sorter >::sortC ( )

private

Definition at line 219 of file monsort.hpp.

{
  unsigned long i, ir = len, j, k, l = 1, *istack;
  int jstack = 0;
  value a, temp;
  long ncmps;
  int maxstack = 0;
  ncmps = 0;
  istack = newarray_atomic(unsigned long, NSTACK);
  for (;;)
    {
      if (ir - l < THRESH)
        {
          for (j = l + 1; j <= ir; j++)
            {
              a = elems[j];
              for (i = j - 1; i >= l; i--)
                {
                  ncmps++;
                  if (M->compare(elems[i], a) <= 0) break;
                  elems[i + 1] = elems[i];
                }
              elems[i + 1] = a;
            }
          if (jstack == 0) break;
          ir = istack[jstack--];
          l = istack[jstack--];
        }
      else
        {
          k = (l + ir) >> 1;
          SWAP(elems[k], elems[l + 1])
          ncmps++;
          if (M->compare(elems[l], elems[ir]) > 0)
            {
              SWAP(elems[l], elems[ir])
            }
          ncmps++;
          if (M->compare(elems[l + 1], elems[ir]) > 0)
            {
              SWAP(elems[l + 1], elems[ir])
            }
          ncmps++;
          if (M->compare(elems[l], elems[l + 1]) > 0)
            {
              SWAP(elems[l], elems[l + 1])
            }
          i = l + 1;
          j = ir;
          a = elems[l + 1];
          for (;;)
            {
              do
                i++;
              while (ncmps++, M->compare(elems[i], a) < 0);
              do
                j--;
              while (ncmps++, M->compare(elems[j], a) > 0);
              if (j < i) break;
              SWAP(elems[i], elems[j]);
            }
          elems[l + 1] = elems[j];
          elems[j] = a;
          jstack += 2;
          if (jstack > maxstack) maxstack = jstack;
          if (jstack > NSTACK)
            {
              fprintf(stderr, "NSTACK too small in sort.\n");
              exit(0);
            }
          if (ir - i + 1 >= j - l)
            {
              istack[jstack] = ir;
              istack[jstack - 1] = i;
              ir = j - 1;
            }
          else
            {
              istack[jstack] = j - 1;
              istack[jstack - 1] = l;
              l = i;
            }
        }
    }
  freemem(istack);
  fprintf(stderr,
          "quicksort: len = %ld ncmps = %ld 2*depth = %d\n",
          len,
          ncmps,
          maxstack);
}

References elems, freemem(), len, M, newarray_atomic, NSTACK, SWAP, and THRESH.

Referenced by sort().