dsmiley commented on pull request #426: URL: https://github.com/apache/lucene/pull/426#issuecomment-961979683
> I think the quality of the in-place merge sort is to be stable, and more efficient (O(n.log(n)) on larger arrays than the binary sort or insertion sort (O(n2)). That's not useful advise to a user because we don't offer the latter two. We offer MSBRadixSorter, IntroSorter, InPlaceMergeSorter and TimSorter. I'm approaching this from a user's perspective who doesn't work on sorting algorithms. We have a number of options and they should have documentation that helps me/us decide which to used based on the situation. The current docs and even with my minor changes are confusing. Based on what I've found here so far, my thought-process is to choose a sorting algorithm based on this ranked list: 1. Use MSBRadixSorter if I have strings (includes byte strings / arrays) and don't mind a non-stable sort. 2. Use IntroSorter if I don't mind non-stable sort. _(however I've seen a trick by Adrien in our code somewhere to work-around the lack of stability by adding a number to the sort criteria based on the original position.)_ 3. InPlaceMergeSorter if need a stable sort and the list to sort is typically small. (this is my assessment; could be wrong). 4. Use TimSorter otherwise If my characterization is sub-optimal, lets work out what advise to give in a similar fashion to the above and put this on Sorter's class javadocs so we have one place to point users. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
