de.caff.generics.algorithm

## Class DualPivotQuicksort

- java.lang.Object
- - de.caff.generics.algorithm.DualPivotQuicksort

-     public final class DualPivotQuicksort
      extends java.lang.Object

  This class implements the Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

  Changes by Rammi: make this class public and allow user-defined order. Because standard order tests for primitive types are fast operations having a user-defined order makes sorting some 50% slower for these types. For test purposes this also allows `sorting generic indexables` like `TimSort`, but tests show that TimSort is faster in most cases.

  Like standard quicksort this sorting algorithm is not stable.

  Since:
    1.7
  Version:
    2011.02.11 m765.827.12i:5\7pm
  Author:
    Vladimir Yaroslavskiy, Jon Bentley, Josh Bloch, Rammi

- - ### Method Summary

    All Methods Static Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `static void` | `sort(byte[] a, ByteOrdering order)` Sorts the specified array in the specified order.
    `static void` | `sort(byte[] a, int left, int right, ByteOrdering order)` Sorts the specified range of the array in the specified order.
    `static void` | `sort(char[] a, CharOrdering order)` Sorts the specified array.
    `static void` | `sort(char[] a, int left, int right, CharOrdering order)` Sorts the specified range of the array.
    `static void` | `sort(double[] a, DoubleOrdering order)` Sorts the specified array according to the specified order.
    `static void` | `sort(double[] a, int left, int right, DoubleOrdering order)` Sorts the specified range of the array according to the specified order.
    `static void` | `sort(float[] a, FloatOrdering order)` Sorts the specified array using the specified order.
    `static void` | `sort(float[] a, int left, int right, FloatOrdering order)` Sorts the specified range of the array.
    `static void` | `sort(int[] a, int left, int right, IntOrdering order)` Sorts the specified range of the array.
    `static void` | `sort(int[] a, IntOrdering order)` Sorts the specified array.
    `static void` | `sort(long[] a, int left, int right, LongOrdering order)` Sorts the specified range of the array.
    `static void` | `sort(long[] a, LongOrdering order)` Sorts the specified array.
    `(package private) static <T> void` | `sort(MutableIndexable<T> a, Ordering<? super T> order)` Sorts the specified mutable int indexable by the given order.
    `static void` | `sort(MutableIntIndexable a)` Sorts the specified mutable int indexable by the natural order of the elements.
    `static void` | `sort(MutableIntIndexable a, IntOrdering order)` Sorts the specified mutable int indexable by the given order.
    `static void` | `sort(short[] a, int left, int right, ShortOrdering order)` Sorts the specified range of the array.
    `static void` | `sort(short[] a, ShortOrdering order)` Sorts the specified array.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Method Detail

    - #### sort

          public static void sort(int[] a,
                                  @NotNull
                                  IntOrdering order)

      Sorts the specified array.
      Parameters:
        `a` - the array to be sorted
        `order` - user-defined order

    - #### sort

          public static void sort(int[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  IntOrdering order)

      Sorts the specified range of the array.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - user-defined order

    - #### sort

          public static void sort(long[] a,
                                  @NotNull
                                  LongOrdering order)

      Sorts the specified array.
      Parameters:
        `a` - the array to be sorted
        `order` - sort order

    - #### sort

          public static void sort(long[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  LongOrdering order)

      Sorts the specified range of the array.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  short[] a,
                                  @NotNull
                                  ShortOrdering order)

      Sorts the specified array.
      Parameters:
        `a` - the array to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  short[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  ShortOrdering order)

      Sorts the specified range of the array.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  char[] a,
                                  @NotNull
                                  CharOrdering order)

      Sorts the specified array.
      Parameters:
        `a` - the array to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  char[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  CharOrdering order)

      Sorts the specified range of the array.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  byte[] a,
                                  @NotNull
                                  ByteOrdering order)

      Sorts the specified array in the specified order.
      Parameters:
        `a` - the array to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  byte[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  ByteOrdering order)

      Sorts the specified range of the array in the specified order.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  float[] a,
                                  @NotNull
                                  FloatOrdering order)

      Sorts the specified array using the specified order.
      Parameters:
        `a` - the array to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  float[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  FloatOrdering order)

      Sorts the specified range of the array.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - sort order

    - #### sort

          public static void sort(@NotNull
                                  double[] a,
                                  @NotNull
                                  DoubleOrdering order)

      Sorts the specified array according to the specified order.
      Parameters:
        `a` - the array to be sorted
        `order` - sort order

    - #### sort

          public static void sort(double[] a,
                                  int left,
                                  int right,
                                  @NotNull
                                  DoubleOrdering order)

      Sorts the specified range of the array according to the specified order.
      Parameters:
        `a` - the array to be sorted
        `left` - the index of the first element, inclusive, to be sorted
        `right` - the index of the last element, inclusive, to be sorted
        `order` - sort order

    - #### sort

          static <T> void sort(@NotNull
                               MutableIndexable<T> a,
                               @NotNull
                               Ordering<? super T> order)

      Sorts the specified mutable int indexable by the given order. This is some 40% slower than the array method, therefore it's only kept to allow testing.
      Type Parameters:
        `T` - element type
      Parameters:
        `a` - the indexable to be sorted
        `order` - user-defined order

    - #### sort

          public static void sort(@NotNull
                                  MutableIntIndexable a)

      Sorts the specified mutable int indexable by the natural order of the elements.
      Parameters:
        `a` - the int indexable to be sorted

    - #### sort

          public static void sort(@NotNull
                                  MutableIntIndexable a,
                                  @NotNull
                                  IntOrdering order)

      Sorts the specified mutable int indexable by the given order.
      Parameters:
        `a` - the indexable to be sorted
        `order` - user-defined order