http://lucene.apache.org/lucene-parent/lucene-core: Apache Lucene Java Core (The Apache Software Foundation) 
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.util;



import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.RandomAccess;


Methods for manipulating (sorting) collections.
Sort methods work directly on the supplied lists and don't copy to/from arrays
before/after. For medium size collections as used in the Lucene indexer that is
much more efficient.

@lucene.internal
/**
 * Methods for manipulating (sorting) collections.
 * Sort methods work directly on the supplied lists and don't copy to/from arrays
 * before/after. For medium size collections as used in the Lucene indexer that is
 * much more efficient.
 *
 * @lucene.internal
 */

public final class CollectionUtil {

  private CollectionUtil() {} // no instance
  private static final class ListIntroSorter<T> extends IntroSorter {

    T pivot;
    final List<T> list;
    final Comparator<? super T> comp;

    ListIntroSorter(List<T> list, Comparator<? super T> comp) {
      super();
      if (!(list instanceof RandomAccess))
        throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
      this.list = list;
      this.comp = comp;
    }

    @Override
    protected void setPivot(int i) {
      pivot = list.get(i);
    }

    @Override
    protected void swap(int i, int j) {
      Collections.swap(list, i, j);
    }

    @Override
    protected int compare(int i, int j) {
      return comp.compare(list.get(i), list.get(j));
    }

    @Override
    protected int comparePivot(int j) {
      return comp.compare(pivot, list.get(j));
    }

  }

  private static final class ListTimSorter<T> extends TimSorter {

    final List<T> list;
    final Comparator<? super T> comp;
    final T[] tmp;

    @SuppressWarnings("unchecked")
    ListTimSorter(List<T> list, Comparator<? super T> comp, int maxTempSlots) {
      super(maxTempSlots);
      if (!(list instanceof RandomAccess))
        throw new IllegalArgumentException("CollectionUtil can only sort random access lists in-place.");
      this.list = list;
      this.comp = comp;
      if (maxTempSlots > 0) {
        this.tmp = (T[]) new Object[maxTempSlots];
      } else {
        this.tmp = null;
      }
    }

    @Override
    protected void swap(int i, int j) {
      Collections.swap(list, i, j);
    }

    @Override
    protected void copy(int src, int dest) {
      list.set(dest, list.get(src));
    }

    @Override
    protected void save(int i, int len) {
      for (int j = 0; j < len; ++j) {
        tmp[j] = list.get(i + j);
      }
    }

    @Override
    protected void restore(int i, int j) {
      list.set(j, tmp[i]);
    }

    @Override
    protected int compare(int i, int j) {
      return comp.compare(list.get(i), list.get(j));
    }

    @Override
    protected int compareSaved(int i, int j) {
      return comp.compare(tmp[i], list.get(j));
    }

  }

  
Sorts the given random access List using the Comparator. The list must implement RandomAccess. This method uses the intro sort algorithm, but falls back to insertion sort for small lists. 
Throws:
/**
   * Sorts the given random access {@link List} using the {@link Comparator}.
   * The list must implement {@link RandomAccess}. This method uses the intro sort
   * algorithm, but falls back to insertion sort for small lists.
   * @throws IllegalArgumentException if list is e.g. a linked list without random access.
   */
  public static <T> void introSort(List<T> list, Comparator<? super T> comp) {
    final int size = list.size();
    if (size <= 1) return;
    new ListIntroSorter<>(list, comp).sort(0, size);
  }
  
  
Sorts the given random access List in natural order. The list must implement RandomAccess. This method uses the intro sort algorithm, but falls back to insertion sort for small lists. 
Throws:
/**
   * Sorts the given random access {@link List} in natural order.
   * The list must implement {@link RandomAccess}. This method uses the intro sort
   * algorithm, but falls back to insertion sort for small lists.
   * @throws IllegalArgumentException if list is e.g. a linked list without random access.
   */
  public static <T extends Comparable<? super T>> void introSort(List<T> list) {
    final int size = list.size();
    if (size <= 1) return;
    introSort(list, Comparator.naturalOrder());
  }

  // Tim sorts:
  
  
Sorts the given random access List using the Comparator. The list must implement RandomAccess. This method uses the Tim sort algorithm, but falls back to binary sort for small lists. 
Throws:
/**
   * Sorts the given random access {@link List} using the {@link Comparator}.
   * The list must implement {@link RandomAccess}. This method uses the Tim sort
   * algorithm, but falls back to binary sort for small lists.
   * @throws IllegalArgumentException if list is e.g. a linked list without random access.
   */
  public static <T> void timSort(List<T> list, Comparator<? super T> comp) {
    final int size = list.size();
    if (size <= 1) return;
    new ListTimSorter<>(list, comp, list.size() / 64).sort(0, size);
  }
  
  
Sorts the given random access List in natural order. The list must implement RandomAccess. This method uses the Tim sort algorithm, but falls back to binary sort for small lists. 
Throws:
/**
   * Sorts the given random access {@link List} in natural order.
   * The list must implement {@link RandomAccess}. This method uses the Tim sort
   * algorithm, but falls back to binary sort for small lists.
   * @throws IllegalArgumentException if list is e.g. a linked list without random access.
   */
  public static <T extends Comparable<? super T>> void timSort(List<T> list) {
    final int size = list.size();
    if (size <= 1) return;
    timSort(list, Comparator.naturalOrder());
  }

}