It really depends on what you are sorting as to which is fastest. In Java and Python, sorting requires function calls for the comparisons, so it's worth doing fewer comparisons, even at the cost of more memory movement. Timsort is good at that particular trade-off.
I have an implementation of timsort (and may others) in C available at https://github.com/swenson/sort If you are doing multiprocessor sorting of what is too big to fit into an array, you'll likely want to do a hybrid approach, like quick sort locally + external merge sort passes. It is possible to parallelize timsort -- it is mostly just a carefully controlled, unbalanced merge sort, so you can parallelize it in similar ways. --Christopher On Wed, Sep 7, 2016 at 3:58 AM, Russel Winder <[email protected]> wrote: > I see Sort.sort is really Sort.quicksort. I think Java and Python have > both agreed Modified Timsort beats both Quicksort and Merge Sort for > speed, accuracy and stability. Is anyone adding an implementation? > > I also see that Sort.quicksort is explicitly stated as being sequential > (which it is), Merge Sort can be parallelised. I need to find out about > Modified Timsort and whether there is a parallel version. > > -- > Russel. > ============================================================ > ================= > Dr Russel Winder t: +44 20 7585 2200 voip: > sip:[email protected] > 41 Buckmaster Road m: +44 7770 465 077 xmpp: [email protected] > London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder > ------------------------------------------------------------ > ------------------ > > _______________________________________________ > Chapel-developers mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/chapel-developers > >
------------------------------------------------------------------------------
_______________________________________________ Chapel-developers mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/chapel-developers
