The constant factor in radix sort isn't the number of bits, it's the number of digits. Since one typically sorts on a computer using 8-bit 'digits', that's a constant factor of 4 or 8 (not 32 or 64).
Timsort is your first choice.
If sorting became a bottleneck, I'd literally look at every possible approach to speed it up that I could find before considering improving the sorting algorithm. Starting with trying to figure out how to throw around less data while trying to solve the problem.
It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
One, I've asked. Not implementing sort, but implementing complex compare() functions for sortable values. There are many things I can accept as flaws in a coworker but inability to deal with 3 conditionals at once isn't one of them. And I've had people (interviewed or worse, worked with) who can't sort by last name, first name, age.
The other is the "I gave you code now tell me what's wrong with it" answer but that's not writing a sort algorithm, that's detecting that someone needs a better one.
Personally, I'd be all too happy if we stop interviewing people expecting answers that would never pass a code review. I'd say it's hypocritical but it's not even that. It's just wrong headed, and gives bad information to the candidate.
There may be better ways to assess that, though. For example, you could ask them to give one or two examples each of algorithms that are O(1), O(log N), O(N), O(N log N), and O(N^2), and O(something worse than N^2).
Generate all permutations of the data. Stop when one of them is in order.
O(n*n!).
Traditional technical interviews don't seem to help you find the best candidates (Google famously studied their interview process and decided it was no better than chance).
So maybe don't do a technical interview. Or if you do, just take a couple of real problems from work.
If you're making a lot of hires, do some research and run a RCT.
The memorizers in this industry often get jobs higher up the tree and therefore they are highly represented in the hiring practices.
Anyways, I completely agree with you. In my opinion it is essential to KNOW that you DON'T KNOW (i.e. you don't remember how exactly an RB tree works, you just know there is such a thing). Everything else is just a quick Google session away.
I think in practice the answer to the question "which should I use" (rather than "which should ideally be used") is the best developed hybrid sort library for the platform. Beyond the suitable case for insertion sort, its a really substantial job for an individual to develop, test and optimize a high performance sort library that can handle a range of distribution types.
Whether that is true depends on a combination of how much data you have, what kind of data you have, and your programming language's low-level representation.
For ints in C++ and a list of 20 elements, it will be reliably true. For strings in Perl with a list of 500 elements, it reliably won't be true.
On my firefox browser the paragraphs and elements in the table and writeups are somewhat excessively spaced vertically.
Would be nice to see mention of parallel sorting algorithms. These have basically linear speedup and you can do them on GPUs.
Obvious disclaimer that you should never care about your sorting algorithm choice until you need to. Performance is more often IO or memory related than compute. Tech interviews are daft, etc.
I'm gonna actually change the space complexity in the table for both counting sort and radix sort to O(n)--that at least matches the amount of hand-waviness we used for the time costs for those two in the table.