• Type: Improvement Improvement
    • Status: Closed
    • Priority: Trivial Trivial
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.4
    • Component/s: None
    • Labels:
    • Lucene Fields:


      When working on TimSort (LUCENE-4839), I was a little frustrated of not being able to add galloping support because it would have required to add new primitive operations in addition to compare and swap.

      I started working on a prototype that uses inheritance to allow some sorting algorithms to rely on additional primitive operations. You can have a look at (but beware it is a prototype and still misses proper documentation and good tests).

      I think it would offer several advantages:

      • no more need to implement setPivot and comparePivot when using in-place merge sort or insertion sort,
      • the ability to use faster stable sorting algorithms at the cost of some memory overhead (our in-place merge sort is very slow),
      • the ability to implement properly algorithms that are useful on specific datasets but require different primitive operations (such as TimSort for partially-sorted data).

      If you are interested in comparing these implementations with Arrays.sort, there is a Benchmark class in src/examples.

      What do you think?

      1. LUCENE-4946.patch
        130 kB
        Adrien Grand
      2. LUCENE-4946.patch
        130 kB
        Adrien Grand
      3. LUCENE-4946.patch
        130 kB
        Adrien Grand

        Issue Links


          Adrien Grand made changes -
          Link This issue relates to LUCENE-5140 [ LUCENE-5140 ]
          Steve Rowe made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Adrien Grand made changes -
          Status Open [ 1 ] Resolved [ 5 ]
          Fix Version/s 4.4 [ 12324323 ]
          Resolution Fixed [ 1 ]
          Adrien Grand made changes -
          Attachment LUCENE-4946.patch [ 12581687 ]
          Adrien Grand made changes -
          Attachment LUCENE-4946.patch [ 12581615 ]
          Adrien Grand made changes -
          Field Original Value New Value
          Attachment LUCENE-4946.patch [ 12581611 ]
          Adrien Grand created issue -


            • Assignee:
              Adrien Grand
              Adrien Grand
            • Votes:
              0 Vote for this issue
              3 Start watching this issue


              • Created: