1. Lucy
  2. LUCY-49

Context-aware mergesort and quicksort


    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Blocker Blocker
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Core
    • Labels:


      The only sort routine you can count on the system providing is qsort. Some
      systems provide a qsort_r which takes a context argument in addition to the
      items being compared, but not all, and the function signature differs on the
      systems that do provide it (with context being either the first or the last
      argument to the comparison function).

      Lucy::Util::SortUtils provides a context-aware quicksort and a context-aware
      mergesort. The mergesort also exposes merge routines which are optimized for
      use by an external sorter, as they minimize copying.

      The quicksort implementation guards against the classic quicksort worst-case
      behavior with careful pivot selection. One popular quicksort optimization is
      still TODO: using insertion sort for array slices of 10 or fewer elements.
      Implementing that optimization may be worthwhile, as this quicksort will
      probably be used for the first level of token-sorting at index time.

      1. SortUtils.c
        14 kB
        Marvin Humphrey
      2. SortUtils.bp
        3 kB
        Marvin Humphrey


        Transition Time In Source Status Execution Times Last Executer Last Execution Date
        Open Open Resolved Resolved
        1d 1h 52m 1 Marvin Humphrey 15/Sep/09 23:27
        Marvin Humphrey made changes -
        Status Open [ 1 ] Resolved [ 5 ]
        Resolution Fixed [ 1 ]
        Marvin Humphrey added a comment -

        Committed as r815563.

        Marvin Humphrey added a comment - Committed as r815563.
        Marvin Humphrey made changes -
        Field Original Value New Value
        Attachment SortUtils.bp [ 12419566 ]
        Attachment SortUtils.c [ 12419567 ]
        Marvin Humphrey created issue -


          • Assignee:
            Marvin Humphrey
            Marvin Humphrey
          • Votes:
            0 Vote for this issue
            0 Start watching this issue


            • Created: