Lucy
  1. Lucy
  2. LUCY-49

Context-aware mergesort and quicksort

    Details

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

      Description

      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

        Activity

        Hide
        Marvin Humphrey added a comment -

        Committed as r815563.

        Show
        Marvin Humphrey added a comment - Committed as r815563.

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development