"I would like to use parallel_sort in my project and have couple of questions."
Have a look at include/tbb/parallel_sort.h to answer most of them yourself (disregarding the conceptual difference between specification and current implementation).

"1) is the implementation the bitonic sort? otherwise what's the complexity? taking also into account the number of available cores or threads"
Ditto (the name of the internal function parallel_quick_sort() should be a clue). What's your evaluation?

"2) how can I specify how many threads are available to TBB? e.g. in MKL I can say export MKL_NUM_THREADS=1 or whatever"
Have a look at task_scheduler_init (note that it's a type, so don't call it as a function, which would defeat the purpose).

"3) Following on question 2, what kind of sequential implementation parallel_sort defaults to if the number of threads is just one? does it delegate to std::sort?"
It defaults to std::sort below a certain range size, but otherwise just executes the parallel version (it might be interesting to quantify the overhead, which is probably low enough to be disregarded).

I noticed a test "if (my_context.is_group_execution_cancelled())" before some of the code code, which seems strange, but I have not looked any deeper at what's going on. Maybe somebody from the TBB team could offer some reassurance, if it's not a bug?