ScratchQuickSort: a faster version of QuickSort

ScratchQuickSort is a novel variation on QuickSort that is typically faster, always stable, and now Julia's default sorting algorithm for generic data.

By leveraging a scratch space, ScratchQuickSort utilizes a faster partitioning strategy which emits simpler cpu instructions than QuickSort. Specifically the order of comparisons and memory reads is independent of the results of those comparisons allowing better ILP and faster iteration. Due to Julia's integrated sorting pipeline, the scratch space used by ScratchQuickSort is reused throughout the sorting pipeline and is rarely a performance bottleneck.

Nevertheless, ScratchQuickSort is not always faster than ScratchQuickSort and this talk will briefly explain how to avoid those limitations when they do occur

Should time allow, this talk may also describe how ScratchQuickSort is robust to invalid user orderings that cause ScratchQuickSort to segfault and how it ensures stability with negligible performance overhead.

ScratchQuickSort was first published (as far as I can tell) when it was introduced to the Julia programming language in https://github.com/JuliaLang/julia/pull/45222