Question

http://ideone.com/ESeUS why is isortslow orders of magnitude slower than isort? Is it because it's using lots of function calls?

btw, how do I implement a generic mergesort/quicksort in C? I think qsort, a stdlib generic quicksort, is a little known secret in C although it uses a function alias/pointer.

Answer 1

the generic qsort that's part of the C standard library is a little faster than my ssort macro :-(

Answer 2

It's the function calls and the memcpys. Don't forget, every memcpy is in essence a for-loop copying each element. Memcpy implementations are pretty good these days (copying 32- or even 64bit values at a time first, then the remaining bytes, and i've even seen MMX and SSE implementations), but it's still relatively slow.
I'd also avoid the dynamic allocation, but that's a minor point. You should, however, probably either assert or log an error to stderr if the malloc returns 0, instead of silently failing ;)

For the record, for something like this operator overloading in C++ and a templated sort function come in really handy. You'll be able to sort *all* types as long as they implement the comparison operator you use in the sort function, and since it's compile time generated, the calls to the operators are going to end up inlined, as long as they're not huge. If you're trying to use the sort function template on a class that doesn't implement operator <, you'll get a simple undefined symbol compiler error.

Answer 3

yet another reason for me to switch for C to C++ :-D