Optimizing Java using D

[Xinok via Digitalmars-d]

On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu 
wrote:
> On 6/21/14, 8:28 AM, Xinok wrote:
>> That has since been fixed. I implemented heapsort as a fallback
>> algorithm, effectively making it an introsort.
>
> Wait, when did that happen? I think a better solution would be 
> to take median of more than 3 elements. -- Andrei

https://github.com/D-Programming-Language/phobos/pull/1735

I did experiment with taking a median of five. There wasn't much 
benefit to doing so and it added a considerable overhead. I 
decided it best to leave quicksort as it is. If anybody else can 
come up with something better, they're free to do a pull request.

The thing about introsort is that it guarantees non-quadratic 
time with almost zero overhead, something taking the median of N 
elements cannot guarantee... unless you take the median of 
hundreds of elements, which would be incredibly complex and slow.