Lucene - Core
  1. Lucene - Core
  2. LUCENE-4839

Sorter API: Use TimSort to sort doc IDs and postings lists

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      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.

      1. LUCENE-4839.patch
        30 kB
        Adrien Grand
      2. LUCENE-4839.patch
        17 kB
        Adrien Grand

        Issue Links

          Activity

          No work has yet been logged on this issue.

            People

            • Assignee:
              Adrien Grand
              Reporter:
              Adrien Grand
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development