Array#sort is slower than MRI
-----------------------------
Key: JRUBY-2198
URL: http://jira.codehaus.org/browse/JRUBY-2198
Project: JRuby
Issue Type: Bug
Components: Performance
Reporter: Marcin Mielzynski
Attachments: IntroSorter.java
MRI quick sort implementation modification (rotate quicksort and median of
three) is a non recursive one that's aware of almost sorted and almost reverse
sorted lists. Thus, it is very efficient for those cases as it doesn't call
back for comparison too often.
Java java.util.Arrays.sort implementation is only aware of sorted lists where
it's even better than MRI, though, it doesn't seem to sort in place.
The attached file contains IntroSorter, a quick/insertion sort combo
modification that's ensures Nlog(N) worse time behavior and does pretty good
job on average. Otoh, it's much worse on sorted/reverse sorted lists because it
doesn't perform any sampling (or it's just an algorithm feature?). introsort is
commonly used by STL C++ libraries.
Are we going for this one ?
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://jira.codehaus.org/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe from this list, please visit:
http://xircles.codehaus.org/manage_email
