TLDR is that Julia uses an algorithm called Scratch quick sort that uses an allocation in order to be both faster than regular quicksort and stable. See https://www.youtube.com/watch?v=RIhCBTx5TYA for details (this also might be a case where we use Radix sort which also allocates). We have an API for passing in a scratch buffer to sort but I’m not sure if that is part of the public interface. @Lilith can you confirm?
8 Likes