How I Invented Orasort: A 5X Faster Adaptive Sort Algorithm for Oracle

Common prefix skipping, adaptive sort

I developed a new in-memory sort algorithm called Orasort while working at Oracle, which eventually landed in 10gR2. By using common prefix skipping and adaptively switching between quicksort and radix sort, the algorithm achieved roughly five times the performance of the previous method. I tested this on various hardware, from old PowerPC Macs to Sun servers, proving its efficiency for large database keys despite some worst-case risks.

"And that was all the motivation I needed to leave Oracle -- first for a startup, and then to Google and Facebook."