[LUCENE-4839] Sorter API: Use TimSort to sort doc IDs and postings lists

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Fixed
• Lucene Fields: New
• Assignee: Adrien Grand
• Reporter: Adrien Grand
• Created: 16/Mar/13 14:19
• Updated: 16/Mar/13 22:36
• Resolved: 16/Mar/13 16:49

Description

TimSort (http://svn.python.org/projects/python/trunk/Objects/listsort.txt, used by python and Java's Arrays.sort(Object[]) in particular) is a sorting algorithm that performs very well on partially-sorted data. Indeed, with TimSort, sorting an array which is in reverse order or a finite concatenation of sorted arrays is a linear operation (instead of O(n ln)).

The sorter API could benefit from this algorithm when using Sorter.REVERSE_DOCS or merging several sorted readers for example.

Issue Links

• is related to: LUCENE-3918 Port index sorter to trunk APIs