Uploaded image for project: 'IMPALA'
  1. IMPALA
  2. IMPALA-10961

Implement 3-way quicksort in sorter

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Resolved
    • Major
    • Resolution: Fixed
    • None
    • Impala 4.1.0
    • Backend
    • ghx-label-9

    Description

      Using 3-way partitioning in quicksort could massively speed up sorting if there is a large number of duplicate elements. This is very common in sorts before partitioned inserts.

      Attachments

        1. qsort.cc
          9 kB
          Kurt Deschler
        2. checksorted.patch
          4 kB
          Kurt Deschler

        Issue Links

          Activity

            People

              noemi Noemi Pap-Takacs
              csringhofer Csaba Ringhofer
              Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: