Optimizing Java using D

[Andrei Alexandrescu via Digitalmars-d]

On 6/22/14, 7:47 AM, Xinok wrote:
> 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

Thanks. I wonder if it's possible to factor some of the heap sort code 
with the BinaryHeap code; they look very similar.

> 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.

I was thinking of sorting in place a stride (every k elements in the 
original array) first; then the median is the middle of the stride. The 
length of the stride would be proportional to log(n).

Anyhow, I see you have a test with this array:

foreach(k; 0..arr.length) arr[k] = k;
swapRanges(arr[0..$/2], arr[$/2..$]);

and you count the comparisons. Nice! We should add arrays with other 
statistics, too (e.g.: presorted, random uniform, random Gaussian). Also 
we should count the number of swaps, the other primitive operation in 
sorting.

> 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.

http://dlang.org/phobos/std_algorithm.html#topN is linear.


Andrei