IntroSorter

java.lang.Object
- org.apache.lucene.util.Sorter
- - org.apache.lucene.util.IntroSorter

Direct Known Subclasses:

ArrayIntroSorter, CollectionUtil.ListIntroSorter
```
public abstract class IntroSorter
extends Sorter
```
Sorter implementation based on a variant of the quicksort algorithm called introsort: when the recursion level exceeds the log of the length of the array to sort, it falls back to heapsort. This prevents quicksort from running into its worst-case quadratic runtime. Small arrays are sorted with insertion sort.

Field Summary
- Fields inherited from class org.apache.lucene.util.Sorter
  BINARY_SORT_THRESHOLD

Constructor Summary

Constructors
Constructor Description

IntroSorter()
Create a new IntroSorter.

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
Modifier and Type	Method	Description
`protected int`	`compare(int i, int j)`	Compare entries found in slots `i` and `j`.
`protected abstract int`	`comparePivot(int j)`	Compare the pivot with the slot at `j`, similarly to `compare(i, j)`.
`(package private) void`	`quicksort(int from, int to, int maxDepth)`
`protected abstract void`	`setPivot(int i)`	Save the value at slot `i` so that it can later be used as a pivot, see `Sorter.comparePivot(int)`.
`void`	`sort(int from, int to)`	Sort the slice which starts at `from` (inclusive) and ends at `to` (exclusive).

Methods inherited from class org.apache.lucene.util.Sorter
binarySort, binarySort, checkRange, doRotate, heapChild, heapify, heapParent, heapSort, lower, lower2, mergeInPlace, reverse, rotate, siftDown, swap, upper, upper2

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - IntroSorter
```
public IntroSorter()
```
    Create a new IntroSorter.
- Method Detail
  - sort
```
public final void sort(int from,
                       int to)
```
    Description copied from class: Sorter
    
    Sort the slice which starts at from (inclusive) and ends at to (exclusive).
    
    Specified by:
    
    sort in class Sorter
  - quicksort
```
void quicksort(int from,
               int to,
               int maxDepth)
```
  - setPivot
```
protected abstract void setPivot(int i)
```
    Description copied from class: Sorter
    
    Save the value at slot i so that it can later be used as a pivot, see Sorter.comparePivot(int).
    
    Overrides:
    
    setPivot in class Sorter
  - comparePivot
```
protected abstract int comparePivot(int j)
```
    Description copied from class: Sorter
    
    Compare the pivot with the slot at j, similarly to compare(i, j).
    
    Overrides:
    
    comparePivot in class Sorter
  - compare
```
protected int compare(int i,
                      int j)
```
    Description copied from class: Sorter
    
    Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).
    
    Specified by:
    
    compare in class Sorter