Uploaded image for project: 'Hadoop Common'
  1. Hadoop Common
  2. HADOOP-3308

Improve QuickSort by excluding values eq the pivot from the partition

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 0.18.0
    • None
    • None
    • Reviewed

    Description

      The current implementation of QuickSort naively partitions on either side of the pivot. We can improve this by partitioning on either side of the set of values equal to the pivot. This assumes that comparing keys is expensive compared to swaps and index comparisons (which it certainly is in MapTask, and should be in general).

      Attachments

        1. 3308-0.patch
          5 kB
          Christopher Douglas
        2. 3308-1.patch
          5 kB
          Christopher Douglas
        3. 3308-2.patch
          6 kB
          Christopher Douglas

        Activity

          People

            cdouglas Christopher Douglas
            cdouglas Christopher Douglas
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: