You can implement merge sort in place too:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....

Looks like the algo is more complicated, but surely implementable. In most modern architectures, the key for performance is how one exploits the caching behavior. Quicksort is very cache friendly, as well as the common implementation of merge sort. Not so for heapsort.

"The O(n) extra-space required by mergesort isn't always available."

Heapsort

No, but mergesort can easily fall back to dumping its sorted contents to disk, for later merging; this disk-based merge sort was invented by van Neumann in the 1940s, and is how the unix utility sort works (dozen-way merge of sorted shards of a file).

Mergesort gets pretty damn efficient, even with moderate buffer space.

Considering the fact that timing attacks based on memcmp short circuiting were shown to be remotely practical a decade ago, latency isn't going to be an issue. The bigger question is whether you can get down your inputs to a small enough number to practically determine PRNG state (you probably can).

One attack and obfuscate the other. Like if you server is at 90% cpu use, and the vast majority of it is server application. You won't consider anything strange happening. You can keep attacking the system with strange algorithm exploits or stop. Nobody will expect an attack in the system since well last time I check the box was at 90% CPU, and it was the server. I'd check again, but maybe we just have a lot of traffic today or something similar.

Basically its the old, can't see the forest past the trees routine.

Its more gaming the operators then the system.

True, but parent meant used in the qsort and qsort_r implementations.

It now reports overflow instead of crashing, but the first case is still incorrect:

  $ which expr

  /bin/expr

  $ expr \( -9223372036854775808 \) \* -1

  -9223372036854775808

  $ expr \( -9223372036854775808 \) / -1 

  expr: overflow

Looking at the source code:

  void

  assert_times(intmax_t a, intmax_t b, intmax_t r)

  {

          /*

           * if first operand is 0, no overflow is possible,

           * else result of division test must match second operand

           */

          if (a != 0 && r / a != b)

                  errx(ERR_EXIT, "overflow");

    }


  struct val *

  op_times(struct val *a, struct val *b)

  {

          struct val *r;


          assert_to_integer(a);

          assert_to_integer(b);

          r = make_integer(a->u.i * b->u.i);

          assert_times(a->u.i, b->u.i, r->u.i);


          free_value(a);

          free_value(b);

          return (r);

  }


  void

  assert_div(intmax_t a, intmax_t b)

  {

          if (b == 0)

                  errx(ERR_EXIT, "division by zero");

          /* only INTMAX_MIN / -1 causes overflow */

          if (a == INTMAX_MIN && b == -1)

                  errx(ERR_EXIT, "overflow");

  }


  struct val *

  op_div(struct val *a, struct val *b)

  {

          struct val *r;

          assert_to_integer(a);

          assert_to_integer(b);

          /* assert based on operands only, not on result */

          assert_div(a->u.i, b->u.i);

          r = make_integer(a->u.i / b->u.i);

          free_value(a);

          free_value(b);

          return (r);

  }

Looks like the check for overflow in the multiplication case is broken since the check itself does not account for overflow. I'll try to remember to submit a patch when I get home.