Overview | Package | Class | Use | Tree | Deprecated | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.lucene.util
Class TimSorter

    java.lang.Object
      org.apache.lucene.util.Sorter
          org.apache.lucene.util.TimSorter

    public abstract class TimSorter

extends Sorter

`Sorter` implementation based on the TimSort algorithm.

This implementation is especially good at sorting partially-sorted arrays and sorts small arrays with binary sort.

NOTE:There are a few differences with the original implementation:

- The extra amount of memory to perform merges is configurable. This allows small merges to be very fast while large merges will be performed in-place (slightly slower). You can make sure that the fast merge routine will always be used by having `maxTempSlots` equal to half of the length of the slice of data to sort.
- Only the fast merge routine can gallop (the one that doesn't run in-place) and it only gallops on the longest slice.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Constructor Summary
`protected` | `TimSorter(int maxTempSlots)` Create a new `TimSorter`.

Method Summary
`protected abstract int` | `compareSaved(int i, int j)` Compare element `i` from the temporary storage with element `j` from the slice to sort, similarly to `Sorter.compare(int, int)`.
`protected abstract void` | `copy(int src, int dest)` Copy data from slot `src` to slot `dest`.
`protected abstract void` | `restore(int i, int j)` Restore element `j` from the temporary storage into slot `i`.
`protected abstract void` | `save(int i, int len)` Save all elements between slots `i` and `i+len` into the temporary storage.
`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
`compare, swap`

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

Constructor Detail

### TimSorter

    protected TimSorter(int maxTempSlots)

  Create a new `TimSorter`.

  Parameters:
    `maxTempSlots` - the maximum amount of extra memory to run merges

Method Detail

### sort

    public 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`

### copy

    protected abstract void copy(int src,
                                 int dest)

  Copy data from slot `src` to slot `dest`.

### save

    protected abstract void save(int i,
                                 int len)

  Save all elements between slots `i` and `i+len` into the temporary storage.

### restore

    protected abstract void restore(int i,
                                    int j)

  Restore element `j` from the temporary storage into slot `i`.

### compareSaved

    protected abstract int compareSaved(int i,
                                        int j)

  Compare element `i` from the temporary storage with element `j` from the slice to sort, similarly to `Sorter.compare(int, int)`.

Overview | Package | Class | Use | Tree | Deprecated | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2000-2013 Apache Software Foundation. All Rights Reserved.