svn commit: r1479109 [1/2] - in /commons/sandbox/sorting/trunk: ./ src/ src/main/ src/main/java/ src/main/java/org/ src/main/java/org/apache/ src/main/java/org/apache/commons/ src/main/java/org/apache/commons/sorting/ src/test/ src/test/java/ src/test/...

[jp...@apache.org]

Author: jpountz
Date: Sat May  4 13:55:17 2013
New Revision: 1479109

URL: http://svn.apache.org/r1479109
Log:
Initial code check-in.

Added:
    commons/sandbox/sorting/trunk/LICENSE.txt   (with props)
    commons/sandbox/sorting/trunk/NOTICE.txt   (with props)
    commons/sandbox/sorting/trunk/pom.xml   (with props)
    commons/sandbox/sorting/trunk/src/
    commons/sandbox/sorting/trunk/src/main/
    commons/sandbox/sorting/trunk/src/main/java/
    commons/sandbox/sorting/trunk/src/main/java/org/
    commons/sandbox/sorting/trunk/src/main/java/org/apache/
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/BinarySorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/HeapSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InPlaceMergeSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InsertionSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/IntroSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/MergeSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/Sorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TernaryHeapSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TimSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/package.html   (with props)
    commons/sandbox/sorting/trunk/src/main/java/overview.html   (with props)
    commons/sandbox/sorting/trunk/src/test/
    commons/sandbox/sorting/trunk/src/test/java/
    commons/sandbox/sorting/trunk/src/test/java/org/
    commons/sandbox/sorting/trunk/src/test/java/org/apache/
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayBinarySorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayHeapSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInPlaceMergeSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInsertionSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayIntroSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayMergeSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTernaryHeapSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTimSorter.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Benchmark.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/BinarySorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/Entry.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/HeapSorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InPlaceMergeSorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/InsertionSorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/IntroSorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/MergeSorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SortTestBase.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/SorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TernaryHeapSorterTest.java   (with props)
    commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/TimSorterTest.java   (with props)
Modified:
    commons/sandbox/sorting/trunk/   (props changed)

Propchange: commons/sandbox/sorting/trunk/
------------------------------------------------------------------------------
--- svn:ignore (added)
+++ svn:ignore Sat May  4 13:55:17 2013
@@ -0,0 +1,5 @@
+target
+.externalToolBuilders
+.settings
+.project
+.classpath

Added: commons/sandbox/sorting/trunk/LICENSE.txt
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/LICENSE.txt?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/LICENSE.txt (added)
+++ commons/sandbox/sorting/trunk/LICENSE.txt Sat May  4 13:55:17 2013
@@ -0,0 +1,202 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed 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.

Propchange: commons/sandbox/sorting/trunk/LICENSE.txt
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/NOTICE.txt
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/NOTICE.txt?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/NOTICE.txt (added)
+++ commons/sandbox/sorting/trunk/NOTICE.txt Sat May  4 13:55:17 2013
@@ -0,0 +1,5 @@
+Apache Commons Sorting
+Copyright 2013 The Apache Software Foundation
+
+This product includes software developed at
+The Apache Software Foundation (http://www.apache.org/).

Propchange: commons/sandbox/sorting/trunk/NOTICE.txt
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/pom.xml
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/pom.xml?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/pom.xml (added)
+++ commons/sandbox/sorting/trunk/pom.xml Sat May  4 13:55:17 2013
@@ -0,0 +1,116 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+   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.
+-->
+<project
+    xmlns="http://maven.apache.org/POM/4.0.0"
+    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+
+  <modelVersion>4.0.0</modelVersion>
+
+  <parent>
+    <groupId>org.apache.commons</groupId>
+    <artifactId>commons-sandbox-parent</artifactId>
+    <version>10</version>
+  </parent>
+
+  <groupId>org.apache.commons</groupId>
+  <artifactId>commons-sorting</artifactId>
+  <version>1.0-SNAPSHOT</version>
+  <name>Commons Sorting</name>
+  <url>http://commons.apache.org/sandbox/sorting/</url>
+  <description>
+Sorting abstraction aiming at maiking any random-access list-like data-structure easily sortable.
+  </description>
+
+  <properties>
+    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
+    <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
+    <maven.compile.source>1.5</maven.compile.source>
+    <maven.compile.target>1.5</maven.compile.target>
+    <commons.componentid>sorting</commons.componentid>
+  </properties>
+
+  <dependencies>
+    <dependency>
+      <groupId>com.carrotsearch.randomizedtesting</groupId>
+      <artifactId>randomizedtesting-runner</artifactId>
+      <version>2.0.9</version>
+      <scope>test</scope>
+    </dependency>
+  </dependencies>
+
+  <developers>
+    <developer>
+      <name>Adrien Grand</name>
+      <id>jpountz</id>
+      <email>jpountz at apache.org</email>
+    </developer>
+  </developers>
+
+  <contributors>
+  </contributors>
+
+  <scm>
+    <connection>scm:svn:http://svn.apache.org/repos/asf/commons/sandbox/sorting/trunk</connection>
+    <developerConnection>scm:svn:https://svn.apache.org/repos/asf/commons/commons/sorting/trunk</developerConnection>
+    <url>http://svn.apache.org/repos/asf/commons/sandbox/sorting/trunk</url>
+  </scm>
+
+  <build>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <configuration>
+          <source>${maven.compile.source}</source>
+          <target>${maven.compile.target}</target>
+        </configuration>
+      </plugin>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-surefire-plugin</artifactId>
+        <configuration>
+          <skipTests>true</skipTests>
+        </configuration>
+      </plugin>
+      <plugin>
+        <groupId>com.carrotsearch.randomizedtesting</groupId>
+        <artifactId>junit4-maven-plugin</artifactId>
+        <version>2.0.8</version>
+        <executions>
+          <execution>
+            <id>tests</id>
+            <phase>test</phase>
+            <goals>
+              <goal>junit4</goal>
+            </goals>
+            <configuration>
+              <!-- configuration overrides. -->
+            </configuration>
+          </execution>
+        </executions>
+      </plugin>
+    </plugins>
+  </build>
+
+  <reporting>
+    <plugins>
+    </plugins>
+  </reporting>
+
+</project>

Propchange: commons/sandbox/sorting/trunk/pom.xml
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/BinarySorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/BinarySorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/BinarySorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/BinarySorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,35 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+/**
+ * A {@link Sorter} implementation based on the binary sort algorithm.
+ * <p>This sort algorithm is stable and is best used on small arrays.
+ */
+public abstract class BinarySorter extends Sorter {
+
+  /** Create a new {@link BinarySorter}. */
+  public BinarySorter() {}
+
+  @Override
+  public final void sort(int from, int to) {
+    checkRange(from, to);
+    binarySort(from, to);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/BinarySorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/HeapSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/HeapSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/HeapSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/HeapSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,34 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+/**
+ * A {@link Sorter} implementation based on the heap-sort algorithm.
+ */
+public abstract class HeapSorter extends Sorter {
+
+  /** Create a new {@link HeapSorter}. */
+  public HeapSorter() {}
+
+  @Override
+  public void sort(int from, int to) {
+    checkRange(from, to);
+    heapSort(from, to);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/HeapSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InPlaceMergeSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InPlaceMergeSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InPlaceMergeSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InPlaceMergeSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,45 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+/** {@link Sorter} implementation based on the merge-sort algorithm that merges
+ *  in place (no extra memory will be allocated). Small arrays are sorted with
+ *  {@link InsertionSorter}. */
+public abstract class InPlaceMergeSorter extends Sorter {
+
+  /** Create a new {@link InPlaceMergeSorter} */
+  public InPlaceMergeSorter() {}
+
+  @Override
+  public final void sort(int from, int to) {
+    checkRange(from, to);
+    mergeSort(from, to);
+  }
+
+  void mergeSort(int from, int to) {
+    if (to - from < THRESHOLD) {
+      insertionSort(from, to);
+    } else {
+      final int mid = (from + to) >>> 1;
+      mergeSort(from, mid);
+      mergeSort(mid, to);
+      mergeInPlace(from, mid, to);
+    }
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InPlaceMergeSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InsertionSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InsertionSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InsertionSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InsertionSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,36 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+/**
+ * A {@link Sorter} implementation based on the insertion sort algorithm.
+ * <p>This sort algorithm is stable and is best used on small arrays which are
+ * almost sorted.
+ */
+public abstract class InsertionSorter extends Sorter {
+
+  /** Create a new {@link InsertionSorter} */
+  public InsertionSorter() {}
+
+  @Override
+  public final void sort(int from, int to) {
+    checkRange(from, to);
+    insertionSort(from, to);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/InsertionSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/IntroSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/IntroSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/IntroSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/IntroSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,96 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+/**
+ * {@link Sorter} implementation based on a variant of the quicksort algorithm
+ * called <a href="http://en.wikipedia.org/wiki/Introsort">introsort</a>: 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
+ * {@link InsertionSorter}.
+ */
+public abstract class IntroSorter extends Sorter {
+
+  static int ceilLog2(int n) {
+    return Integer.SIZE - Integer.numberOfLeadingZeros(n - 1);
+  }
+
+  /** Create a new {@link IntroSorter}. */
+  public IntroSorter() {}
+
+  @Override
+  public final void sort(int from, int to) {
+    checkRange(from, to);
+    quicksort(from, to, ceilLog2(to - from));
+  }
+
+  void quicksort(int from, int to, int maxDepth) {
+    if (to - from < THRESHOLD) {
+      insertionSort(from, to);
+      return;
+    } else if (--maxDepth < 0) {
+      heapSort(from, to);
+      return;
+    }
+
+    final int mid = (from + to) >>> 1;
+
+    if (compare(from, mid) > 0) {
+      swap(from, mid);
+    }
+
+    if (compare(mid, to - 1) > 0) {
+      swap(mid, to - 1);
+      if (compare(from, mid) > 0) {
+        swap(from, mid);
+      }
+    }
+
+    int left = from + 1;
+    int right = to - 2;
+
+    setPivot(mid);
+    for (;;) {
+      while (comparePivot(right) < 0) {
+        --right;
+      }
+
+      while (left < right && comparePivot(left) >= 0) {
+        ++left;
+      }
+
+      if (left < right) {
+        swap(left, right);
+        --right;
+      } else {
+        break;
+      }
+    }
+
+    quicksort(from, left + 1, maxDepth);
+    quicksort(left + 1, to, maxDepth);
+  }
+
+  /** Save the value at slot <code>i</code> so that it can later be used as a
+   * pivot, see {@link #comparePivot(int)}. */
+  protected abstract void setPivot(int i);
+
+  /** Compare the pivot with the slot at <code>j</code>, similarly to
+   *  {@link #compare(int, int) compare(i, j)}. */
+  protected abstract int comparePivot(int j);
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/IntroSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/MergeSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/MergeSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/MergeSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/MergeSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,186 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+/**
+ * {@link Sorter} implementation based on the merge-sort algorithm that merges
+ * runs using extra memory (on the contrary to {@link InPlaceMergeSorter}).
+ * Small arrays are sorted with {@link InsertionSorter}.
+ * <p><a name="maxTempSlots"/>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 <code>maxTempSlots</code>
+ * equal to the length of the slice of data to sort.
+ */
+public abstract class MergeSorter extends Sorter {
+
+  private final int maxTempSlots;
+
+  /**
+   * Create a new {@link MergeSorter}.
+   * @param maxTempSlots the <a href="#maxTempSlots">maximum amount of extra memory to run merges</a>
+   */
+  public MergeSorter(int maxTempSlots) {
+    this.maxTempSlots = maxTempSlots;
+  }
+
+  @Override
+  public final void sort(int from, int to) {
+    checkRange(from, to);
+    mergeSort(from, to);
+  }
+
+  void mergeSort(int from, int to) {
+    if (to - from < THRESHOLD) {
+      insertionSort(from, to);
+      return;
+    } else if (to - from > maxTempSlots) {
+      final int mid = (from + to) >>> 1;
+      mergeSort(from, mid);
+      mergeSort(mid, to);
+      mergeInPlace(from, mid, to);
+      return;
+    }
+    final int mid = (from + to) >>> 1;
+    final int q1 = (from + mid) >>> 1;
+    final int q3 = (mid + to) >>> 1;
+    mergeSort(q3, to);
+    mergeSort(mid, q3);
+    mergeSort(q1, mid);
+    mergeSort(from, q1);
+
+    final boolean cq1 = compare(q1 - 1, q1) <= 0;
+    final boolean cq3 = compare(q3 - 1, q3) <= 0;
+
+    if (cq1 && cq3 && compare(mid - 1, mid) <= 0) {
+      // nothing to do
+      return;
+    }
+
+    if (cq1) {
+      saveAll(from, mid, from);
+    } else {
+      merge1(from, q1, mid, from);
+    }
+
+    if (cq3) {
+      saveAll(mid, to, from);
+    } else {
+      merge1(mid, q3, to, from);
+    }
+
+    merge2(from, mid, to, from);
+  }
+
+  void saveAll(int from, int to, int base) {
+    for (int i = from; i < to; ++i) {
+      save(i, i - base);
+    }
+  }
+
+  void merge1(int from, int mid, int to, int base) {
+    int dest = from - base, i = from, j = mid;
+    for ( ; i < mid && j < to; ++dest) {
+      if (compare(i, j) <= 0) {
+        save(i++, dest);
+      } else {
+        save(j++, dest);
+      }
+    }
+    for ( ; i < mid; ++i, ++dest) {
+      save(i, dest);
+    }
+    for ( ; j < to; ++j, ++dest) {
+      save(j, dest);
+    }
+    assert dest == to - base;
+  }
+
+  void merge2(int from, int mid, int to, int base) {
+    if (compareSaved(mid - 1 - base, mid - base) <= 0) {
+      for (int i = from; i < to; ++i) {
+        restore(i - base, i);
+      }
+      return;
+    }
+    final int iend = mid - base, jend = to - base;
+    int dest = from, i = from - base, j = mid - base;
+    for ( ; i < iend && j < jend; ++dest) {
+      if (compareSaved(i, j) <= 0) {
+        restore(i++, dest);
+      } else {
+        restore(j++, dest);
+      }
+    }
+    for ( ; i < iend; ++i, ++dest) {
+      restore(i, dest);
+    }
+    for ( ; j < jend; ++j, ++dest) {
+      restore(j, dest);
+    }
+    assert dest == to;
+  }
+
+  @Override
+  void rotate(int lo, int mid, int hi) {
+    int len1 = mid - lo;
+    int len2 = hi - mid;
+    if (len1 == len2) {
+      while (mid < hi) {
+        swap(lo++, mid++);
+      }
+    } else if (len2 < len1 && len2 <= maxTempSlots) {
+      for (int i = 0; i < len2; ++i) {
+        save(mid + i, i);
+      }
+      for (int i = lo + len1 - 1, j = hi - 1; i >= lo; --i, --j) {
+        copy(i, j);
+      }
+      for (int i = 0, j = lo; i < len2; ++i, ++j) {
+        restore(i, j);
+      }
+    } else if (len1 <= maxTempSlots) {
+      for (int i = 0; i < len1; ++i) {
+        save(lo + i, i);
+      }
+      for (int i = mid, j = lo; i < hi; ++i, ++j) {
+        copy(i, j);
+      }
+      for (int i = 0, j = lo + len2; j < hi; ++i, ++j) {
+        restore(i, j);
+      }
+    } else {
+      reverse(lo, mid);
+      reverse(mid, hi);
+      reverse(lo, hi);
+    }
+  }
+
+  /** Copy data from slot <code>src</code> to slot <code>dest</code>. */
+  protected abstract void copy(int src, int dest);
+
+  /** Save data in slot <code>i</code> in the temporary storage at offset<code>j</code>. */
+  protected abstract void save(int i, int j);
+
+  /** Restore data in slot <code>i</code> of the temporary storage into slot <code>j</code>. */
+  protected abstract void restore(int i, int j);
+
+  /** Compare elements at offsets <code>i</code> and <code>j</code> in the temporary
+   *  storage similarly to {@link #compare(int, int)}. */
+  protected abstract int compareSaved(int i, int j);
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/MergeSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/Sorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/Sorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/Sorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/Sorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,354 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+import java.util.Comparator;
+
+/** Base class for sorting algorithms implementations. */
+public abstract class Sorter {
+
+  static final int THRESHOLD = 20;
+
+  /** Sole constructor, used for inheritance. */
+  protected Sorter() {}
+
+  /** Compare entries found in slots <code>i</code> and <code>j</code>.
+   *  The contract for the returned value is the same as
+   *  {@link Comparator#compare(Object, Object)}. */
+  protected abstract int compare(int i, int j);
+
+  /** Swap values at slots <code>i</code> and <code>j</code>. */
+  protected abstract void swap(int i, int j);
+
+  /** Sort the slice which starts at <code>from</code> (inclusive) and ends at
+   *  <code>to</code> (exclusive). */
+  public abstract void sort(int from, int to);
+
+  void checkRange(int from, int to) {
+    if (to < from) {
+      throw new IllegalArgumentException("'to' must be >= 'from', got from=" + from + " and to=" + to);
+    }
+  }
+
+  void mergeInPlace(int from, int mid, int to) {
+    if (from == mid || mid == to || compare(mid - 1, mid) <= 0) {
+      return;
+    } else if (to - from == 2) {
+      swap(mid - 1, mid);
+      return;
+    }
+    while (compare(from, mid) <= 0) {
+      ++from;
+    }
+    while (compare(mid - 1, to - 1) <= 0) {
+      --to;
+    }
+    int first_cut, second_cut;
+    int len11, len22;
+    if (mid - from > to - mid) {
+      len11 = (mid - from) >>> 1;
+      first_cut = from + len11;
+      second_cut = lower(mid, to, first_cut);
+      len22 = second_cut - mid;
+    } else {
+      len22 = (to - mid) >>> 1;
+      second_cut = mid + len22;
+      first_cut = upper(from, mid, second_cut);
+      len11 = first_cut - from;
+    }
+    rotate( first_cut, mid, second_cut);
+    final int new_mid = first_cut + len22;
+    mergeInPlace(from, first_cut, new_mid);
+    mergeInPlace(new_mid, second_cut, to);
+  }
+
+  int lower(int from, int to, int val) {
+    int len = to - from;
+    while (len > 0) {
+      final int half = len >>> 1;
+      final int mid = from + half;
+      if (compare(mid, val) < 0) {
+        from = mid + 1;
+        len = len - half -1;
+      } else {
+        len = half;
+      }
+    }
+    return from;
+  }
+
+  int upper(int from, int to, int val) {
+    int len = to - from;
+    while (len > 0) {
+      final int half = len >>> 1;
+      final int mid = from + half;
+      if (compare(val, mid) < 0) {
+        len = half;
+      } else {
+        from = mid + 1;
+        len = len - half -1;
+      }
+    }
+    return from;
+  }
+
+  // faster than lower when val is at the end of [from:to[
+  int lower2(int from, int to, int val) {
+    int f = to - 1, t = to;
+    while (f > from) {
+      if (compare(f, val) < 0) {
+        return lower(f, t, val);
+      }
+      final int delta = t - f;
+      t = f;
+      f -= delta << 1;
+    }
+    return lower(from, t, val);
+  }
+
+  // faster than upper when val is at the beginning of [from:to[
+  int upper2(int from, int to, int val) {
+    int f = from, t = f + 1;
+    while (t < to) {
+      if (compare(t, val) > 0) {
+        return upper(f, t, val);
+      }
+      final int delta = t - f;
+      f = t;
+      t += delta << 1;
+    }
+    return upper(f, to, val);
+  }
+
+  final void reverse(int from, int to) {
+    for (--to; from < to; ++from, --to) {
+      swap(from, to);
+    }
+  }
+
+  void rotate(int lo, int mid, int hi) {
+    if (mid - lo == hi - mid) {
+      // happens rarely but saves n/2 swaps
+      while (mid < hi) {
+        swap(lo++, mid++);
+      }
+    } else {
+      reverse(lo, mid);
+      reverse(mid, hi);
+      reverse(lo, hi);
+    }
+  }
+
+  void insertionSort(int from, int to) {
+    for (int i = from + 1; i < to; ++i) {
+      for (int j = i; j > from; --j) {
+        if (compare(j - 1, j) > 0) {
+          swap(j - 1, j);
+        } else {
+          break;
+        }
+      }
+    }
+  }
+
+  void binarySort(int from, int to) {
+    binarySort(from, to, from + 1);
+  }
+
+  void binarySort(int from, int to, int i) {
+    for ( ; i < to; ++i) {
+      int l = from;
+      int h = i - 1;
+      while (l <= h) {
+        final int mid = (l + h) >>> 1;
+        final int cmp = compare(i, mid);
+        if (cmp < 0) {
+          h = mid - 1;
+        } else {
+          l = mid + 1;
+        }
+      }
+      switch (i - l) {
+      case 2:
+        swap(l + 1, l + 2);
+      case 1:
+        swap(l, l + 1);
+      case 0:
+        break;
+      default:
+        for (int j = i; j > l; --j) {
+          swap(j - 1, j);
+        }
+        break;
+      }
+    }
+  }
+
+  void heapSort(int from, int to) {
+    if (to - from <= 1) {
+      return;
+    }
+    heapify(from, to);
+    for (int end = to - 1; end > from; --end) {
+      swap(from, end);
+      siftDown(from, from, end);
+    }
+  }
+
+  void heapify(int from, int to) {
+    for (int i = heapParent(from, to - 1); i >= from; --i) {
+      siftDown(i, from, to);
+    }
+  }
+
+  void siftDown(int i, int from, int to) {
+    for (int leftChild = heapChild(from, i); leftChild < to; leftChild = heapChild(from, i)) {
+      final int rightChild = leftChild + 1;
+      if (compare(i, leftChild) < 0) {
+        if (rightChild < to && compare(leftChild, rightChild) < 0) {
+          swap(i, rightChild);
+          i = rightChild;
+        } else {
+          swap(i, leftChild);
+          i = leftChild;
+        }
+      } else if (rightChild < to && compare(i, rightChild) < 0) {
+        swap(i, rightChild);
+        i = rightChild;
+      } else {
+        break;
+      }
+    }
+  }
+
+  static int heapParent(int from, int i) {
+    return ((i - 1 - from) >>> 1) + from;
+  }
+
+  static int heapChild(int from, int i) {
+    return ((i - from) << 1) + 1 + from;
+  }
+
+  void ternaryHeapSort(int from, int to) {
+    if (to - from <= 1) {
+      return;
+    }
+    heapify3(from, to);
+    for (int end = to - 1; end > from; --end) {
+      swap(from, end);
+      siftDown3(from, from, end);
+    }
+  }
+
+  void heapify3(int from, int to) {
+    for (int i = heapParent3(from, to - 1); i >= from; --i) {
+      siftDown3(i, from, to);
+    }
+  }
+
+  void siftDown3(int i, int from, int to) {
+    for (int leftChild = heapChild3(from, i); leftChild < to; leftChild = heapChild3(from, i)) {
+      final int centerChild = leftChild + 1;
+      final int rightChild = centerChild + 1;
+      if (compare(i, leftChild) < 0) {
+        int child = leftChild;
+        if (centerChild < to && compare(child, centerChild) < 0) {
+          child = centerChild;
+        }
+        if (rightChild < to && compare(child, rightChild) < 0) {
+          child = rightChild;
+        }
+        swap(i, child);
+        i = child;
+      } else if (centerChild < to && compare(i, centerChild) < 0) {
+        if (rightChild < to && compare(centerChild, rightChild) < 0) {
+          swap(i, rightChild);
+          i = rightChild;
+        } else {
+          swap(i, centerChild);
+          i = centerChild;
+        }
+      } else if (rightChild < to && compare(i, rightChild) < 0) {
+        swap(i, rightChild);
+        i = rightChild;
+      } else {
+        break;
+      }
+    }
+  }
+
+  static int heapParent3(int from, int i) {
+    return (i - 1 - from) / 3 + from;
+  }
+
+  static int heapChild3(int from, int i) {
+    return (i - from) * 3 + 1 + from;
+  }
+
+  /* Helper methods */
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static <T> void  swap(T[] arr, int i, int j) {
+    final T tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static void  swap(long[] arr, int i, int j) {
+    final long tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static void  swap(int[] arr, int i, int j) {
+    final int tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static void  swap(double[] arr, int i, int j) {
+    final double tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static void  swap(float[] arr, int i, int j) {
+    final float tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static void  swap(short[] arr, int i, int j) {
+    final short tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+  /** Swap elements at slots <code>i</code> and <code>j</code> in <code>arr</code>. */
+  protected static void  swap(byte[] arr, int i, int j) {
+    final byte tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/Sorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TernaryHeapSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TernaryHeapSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TernaryHeapSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TernaryHeapSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,35 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+/**
+ * A {@link Sorter} implementation based on the heap-sort algorithm on a
+ * ternary heap.
+ */
+public abstract class TernaryHeapSorter extends Sorter {
+
+  /** Create a new {@link TernaryHeapSorter}. */
+  public TernaryHeapSorter() {}
+
+  @Override
+  public void sort(int from, int to) {
+    checkRange(from, to);
+    ternaryHeapSort(from, to);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TernaryHeapSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TimSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TimSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TimSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TimSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,372 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+import java.util.Arrays;
+
+/**
+ * {@link Sorter} implementation based on the
+ * <a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">TimSort</a>
+ * algorithm.
+ * <p>This implementation is especially good at sorting partially-sorted
+ * arrays and sorts small arrays with {@link BinarySorter}.
+ * <p><b>NOTE</b>:There are a few differences with the original implementation:<ul>
+ * <li><a name="maxTempSlots"/>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 <code>maxTempSlots</code>
+ * equal to half of the length of the slice of data to sort.
+ * <li>Only the fast merge routine can gallop (the one that doesn't run
+ * in-place) and it only gallops on the longest slice.
+ * </ul>
+ */
+public abstract class TimSorter extends Sorter {
+
+  static final int MINRUN = 32;
+  static final int THRESHOLD = 64;
+  static final int STACKSIZE = 40; // depends on MINRUN
+  static final int MIN_GALLOP = 7;
+
+  final int maxTempSlots;
+  int minRun;
+  int to;
+  int stackSize;
+  int[] runEnds;
+
+  /**
+   * Create a new {@link TimSorter}.
+   * @param maxTempSlots the <a href="#maxTempSlots">maximum amount of extra memory to run merges</a>
+   */
+  protected TimSorter(int maxTempSlots) {
+    super();
+    runEnds = new int[1 + STACKSIZE];
+    this.maxTempSlots = maxTempSlots;
+  }
+
+  /** Minimum run length for an array of length <code>length</code>. */
+  static int minRun(int length) {
+    assert length >= MINRUN;
+    int n = length;
+    int r = 0;
+    while (n >= 64) {
+      r |= n & 1;
+      n >>>= 1;
+    }
+    final int minRun = n + r;
+    assert minRun >= MINRUN && minRun <= THRESHOLD;
+    return minRun;
+  }
+
+  int runLen(int i) {
+    final int off = stackSize - i;
+    return runEnds[off] - runEnds[off - 1];
+  }
+
+  int runBase(int i) {
+    return runEnds[stackSize - i - 1];
+  }
+
+  int runEnd(int i) {
+    return runEnds[stackSize - i];
+  }
+
+  void setRunEnd(int i, int runEnd) {
+    runEnds[stackSize - i] = runEnd;
+  }
+
+  void pushRunLen(int len) {
+    runEnds[stackSize + 1] = runEnds[stackSize] + len;
+    ++stackSize;
+  }
+
+  /** Compute the length of the next run, make the run sorted and return its
+   *  length. */
+  int nextRun() {
+    final int runBase = runEnd(0);
+    assert runBase < to;
+    if (runBase == to - 1) {
+      return 1;
+    }
+    int o = runBase + 2;
+    if (compare(runBase, runBase+1) > 0) {
+      // run must be strictly descending
+      while (o < to && compare(o - 1, o) > 0) {
+        ++o;
+      }
+      reverse(runBase, o);
+    } else {
+      // run must be non-descending
+      while (o < to && compare(o - 1, o) <= 0) {
+        ++o;
+      }
+    }
+    final int runHi = Math.max(o, Math.min(to, runBase + minRun));
+    binarySort(runBase, runHi, o);
+    return runHi - runBase;
+  }
+
+  void ensureInvariants() {
+    while (stackSize > 1) {
+      final int runLen0 = runLen(0);
+      final int runLen1 = runLen(1);
+
+      if (stackSize > 2) {
+        final int runLen2 = runLen(2);
+
+        if (runLen2 <= runLen1 + runLen0) {
+          // merge the smaller of 0 and 2 with 1
+          if (runLen2 < runLen0) {
+            mergeAt(1);
+          } else {
+            mergeAt(0);
+          }
+          continue;
+        }
+      }
+
+      if (runLen1 <= runLen0) {
+        mergeAt(0);
+        continue;
+      }
+
+      break;
+    }
+  }
+
+  void exhaustStack() {
+    while (stackSize > 1) {
+      mergeAt(0);
+    }
+  }
+
+  void reset(int from, int to) {
+    stackSize = 0;
+    Arrays.fill(runEnds, 0);
+    runEnds[0] = from;
+    this.to = to;
+    final int length = to - from;
+    this.minRun = length <= THRESHOLD ? length : minRun(length);
+  }
+
+  void mergeAt(int n) {
+    assert stackSize >= 2;
+    merge(runBase(n + 1), runBase(n), runEnd(n));
+    for (int j = n + 1; j > 0; --j) {
+      setRunEnd(j, runEnd(j-1));
+    }
+    --stackSize;
+  }
+
+  void merge(int lo, int mid, int hi) {
+    if (compare(mid - 1, mid) <= 0) {
+      return;
+    }
+    lo = upper2(lo, mid, mid);
+    hi = lower2(mid, hi, mid - 1);
+
+    if (hi - mid <= mid - lo && hi - mid <= maxTempSlots) {
+      mergeHi(lo, mid, hi);
+    } else if (mid - lo <= maxTempSlots) {
+      mergeLo(lo, mid, hi);
+    } else {
+      mergeInPlace(lo, mid, hi);
+    }
+  }
+
+  @Override
+  public void sort(int from, int to) {
+    checkRange(from, to);
+    if (to - from <= 1) {
+      return;
+    }
+    reset(from, to);
+    do {
+      ensureInvariants();
+      pushRunLen(nextRun());
+    } while (runEnd(0) < to);
+    exhaustStack();
+    assert runEnd(0) == to;
+  }
+
+  @Override
+  void rotate(int lo, int mid, int hi) {
+    int len1 = mid - lo;
+    int len2 = hi - mid;
+    if (len1 == len2) {
+      while (mid < hi) {
+        swap(lo++, mid++);
+      }
+    } else if (len2 < len1 && len2 <= maxTempSlots) {
+      saveAll(mid, len2);
+      for (int i = lo + len1 - 1, j = hi - 1; i >= lo; --i, --j) {
+        copy(i, j);
+      }
+      for (int i = 0, j = lo; i < len2; ++i, ++j) {
+        restore(i, j);
+      }
+    } else if (len1 <= maxTempSlots) {
+      saveAll(lo, len1);
+      for (int i = mid, j = lo; i < hi; ++i, ++j) {
+        copy(i, j);
+      }
+      for (int i = 0, j = lo + len2; j < hi; ++i, ++j) {
+        restore(i, j);
+      }
+    } else {
+      reverse(lo, mid);
+      reverse(mid, hi);
+      reverse(lo, hi);
+    }
+  }
+
+  void mergeLo(int lo, int mid, int hi) {
+    assert compare(lo, mid) > 0;
+    int len1 = mid - lo;
+    saveAll(lo, len1);
+    copy(mid, lo);
+    int i = 0, j = mid + 1, dest = lo + 1;
+    outer: for (;;) {
+      for (int count = 0; count < MIN_GALLOP; ) {
+        if (i >= len1 || j >= hi) {
+          break outer;
+        } else if (compareSaved(i, j) <= 0) {
+          restore(i++, dest++);
+          count = 0;
+        } else {
+          copy(j++, dest++);
+          ++count;
+        }
+      }
+      // galloping...
+      int next = lowerSaved3(j, hi, i);
+      for (; j < next; ++dest) {
+        copy(j++, dest);
+      }
+      restore(i++, dest++);
+    }
+    for (; i < len1; ++dest) {
+      restore(i++, dest);
+    }
+    assert j == dest;
+  }
+
+  void mergeHi(int lo, int mid, int hi) {
+    assert compare(mid - 1, hi - 1) > 0;
+    int len2 = hi - mid;
+    saveAll(mid, len2);
+    copy(mid - 1, hi - 1);
+    int i = mid - 2, j = len2 - 1, dest = hi - 2;
+    outer: for (;;) {
+      for (int count = 0; count < MIN_GALLOP; ) {
+        if (i < lo || j < 0) {
+          break outer;
+        } else if (compareSaved(j, i) >= 0) {
+          restore(j--, dest--);
+          count = 0;
+        } else {
+          copy(i--, dest--);
+          ++count;
+        }
+      }
+      // galloping
+      int next = upperSaved3(lo, i + 1, j);
+      while (i >= next) {
+        copy(i--, dest--);
+      }
+      restore(j--, dest--);
+    }
+    for (; j >= 0; --dest) {
+      restore(j--, dest);
+    }
+    assert i == dest;
+  }
+
+  int lowerSaved(int from, int to, int val) {
+    int len = to - from;
+    while (len > 0) {
+      final int half = len >>> 1;
+      final int mid = from + half;
+      if (compareSaved(val, mid) > 0) {
+        from = mid + 1;
+        len = len - half -1;
+      } else {
+        len = half;
+      }
+    }
+    return from;
+  }
+
+  int upperSaved(int from, int to, int val) {
+    int len = to - from;
+    while (len > 0) {
+      final int half = len >>> 1;
+      final int mid = from + half;
+      if (compareSaved(val, mid) < 0) {
+        len = half;
+      } else {
+        from = mid + 1;
+        len = len - half -1;
+      }
+    }
+    return from;
+  }
+
+  // faster than lowerSaved when val is at the beginning of [from:to[
+  int lowerSaved3(int from, int to, int val) {
+    int f = from, t = f + 1;
+    while (t < to) {
+      if (compareSaved(val, t) <= 0) {
+        return lowerSaved(f, t, val);
+      }
+      int delta = t - f;
+      f = t;
+      t += delta << 1;
+    }
+    return lowerSaved(f, to, val);
+  }
+
+  //faster than upperSaved when val is at the end of [from:to[
+  int upperSaved3(int from, int to, int val) {
+    int f = to - 1, t = to;
+    while (f > from) {
+      if (compareSaved(val, f) >= 0) {
+        return upperSaved(f, t, val);
+      }
+      final int delta = t - f;
+      t = f;
+      f -= delta << 1;
+    }
+    return upperSaved(from, t, val);
+  }
+
+  /** Copy data from slot <code>src</code> to slot <code>dest</code>. */
+  protected abstract void copy(int src, int dest);
+
+  /** Save all elements between slots <code>i</code> and <code>i+len</code>
+   *  into the temporary storage. */
+  protected abstract void saveAll(int i, int len);
+
+  /** Restore element <code>j</code> from the temporary storage into slot <code>i</code>. */
+  protected abstract void restore(int i, int j);
+
+  /** Compare element <code>i</code> from the temporary storage with element
+   *  <code>j</code> from the slice to sort, similarly to
+   *  {@link #compare(int, int)}. */
+  protected abstract int compareSaved(int i, int j);
+
+}

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/TimSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/package.html
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/package.html?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/package.html (added)
+++ commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/package.html Sat May  4 13:55:17 2013
@@ -0,0 +1,96 @@
+<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
+<!--
+   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.
+-->
+<html>
+<head>
+   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+</head>
+<body>
+Sorting algorithms.
+
+<h2>Comparison</h2>
+<table border="1">
+<tr><th>{@link org.apache.commons.sorting.Sorter}</th><th>Runtime</th><th>Memory</th><th>Stable</th><th>Notes</th></tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.BinarySorter}</td>
+  <td>O(n<sup>2</sup>)</td>
+  <td>O(1)</td>
+  <td>Yes</td>
+  <td>Only for small arrays.</td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.HeapSorter}</td>
+  <td>O(n ln(n))</td>
+  <td>O(1)</td>
+  <td>No</td>
+  <td></td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.InPlaceMergeSorter}</td>
+  <td>O(n ln(n))</td>
+  <td>O(1)</td>
+  <td>Yes</td>
+  <td>O(n) on sorted arrays.</td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.InsertionSorter}</td>
+  <td>O(n<sup>2</sup>)</td>
+  <td>O(1)</td>
+  <td>Yes</td>
+  <td>Only for small or almost sorted arrays.</td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.IntroSorter}</td>
+  <td>O(n ln(n))</td>
+  <td>O(1)</td>
+  <td>No</td>
+  <td>Outperforms other implementations on randomly-sorted data.</td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.MergeSorter}</td>
+  <td>O(n ln(n))</td>
+  <td>n</td>
+  <td>Yes</td>
+  <td>O(n) on sorted arrays, several times faster than {@link org.apache.commons.sorting.InPlaceMergeSorter} on randomly-sorted data.</td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.TernaryHeapSorter}</td>
+  <td>O(n ln(n))</td>
+  <td>O(1)</td>
+  <td>No</td>
+  <td>Slightly faster than {@link org.apache.commons.sorting.HeapSorter} on large arrays.</td>
+</tr>
+<tr>
+  <td>{@link org.apache.commons.sorting.TimSorter}</td>
+  <td>O(n ln(n))</td>
+  <td>Configurable, up to n/2</td>
+  <td>Yes</td>
+  <td>O(n) on partially-sorted data, only slightly slower than {@link org.apache.commons.sorting.MergeSorter} on randomly-sorted data.</td>
+</tr>
+</table>
+
+<h2>Which implementation to use?</h2>
+
+<ul>
+<li>If your data is likely partially sorted, then use {@link org.apache.commons.sorting.TimSorter}.</li>
+<li>Otherwise if you don't need the sort to be stable, then use {@link org.apache.commons.sorting.IntroSorter}.</li>
+<li>Otherwise if you can afford high memory usage, then use {@link org.apache.commons.sorting.MergeSorter}.</li>
+<li>Otherwise use either {@link org.apache.commons.sorting.TimSorter} (faster) or {@link org.apache.commons.sorting.InPlaceMergeSorter} (easier to implement).</li>
+</ul>
+
+</body>
+</html>

Propchange: commons/sandbox/sorting/trunk/src/main/java/org/apache/commons/sorting/package.html
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/main/java/overview.html
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/main/java/overview.html?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/main/java/overview.html (added)
+++ commons/sandbox/sorting/trunk/src/main/java/overview.html Sat May  4 13:55:17 2013
@@ -0,0 +1,26 @@
+<!--
+   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.
+-->
+<html>
+<head>
+   <title>Sorts API</title>
+</head>
+<body>
+
+<p>Flexible implementations of useful sorting algorithms.</p>
+
+</body>
+</html>

Propchange: commons/sandbox/sorting/trunk/src/main/java/overview.html
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayBinarySorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayBinarySorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayBinarySorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayBinarySorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,38 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayBinarySorter<T extends java.lang.Comparable<? super T>> extends BinarySorter {
+
+  private final T[] arr;
+
+  public ArrayBinarySorter(T[] arr) {
+    this.arr = arr;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayBinarySorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayHeapSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayHeapSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayHeapSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayHeapSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,38 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayHeapSorter<T extends java.lang.Comparable<? super T>> extends HeapSorter {
+
+  private final T[] arr;
+
+  public ArrayHeapSorter(T[] arr) {
+    this.arr = arr;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayHeapSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInPlaceMergeSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInPlaceMergeSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInPlaceMergeSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInPlaceMergeSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,38 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayInPlaceMergeSorter<T extends java.lang.Comparable<? super T>> extends InPlaceMergeSorter {
+
+  private final T[] arr;
+
+  public ArrayInPlaceMergeSorter(T[] arr) {
+    this.arr = arr;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInPlaceMergeSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInsertionSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInsertionSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInsertionSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInsertionSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,38 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayInsertionSorter<T extends java.lang.Comparable<? super T>> extends InsertionSorter {
+
+  private final T[] arr;
+
+  public ArrayInsertionSorter(T[] arr) {
+    this.arr = arr;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayInsertionSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayIntroSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayIntroSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayIntroSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayIntroSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,49 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayIntroSorter<T extends java.lang.Comparable<? super T>> extends IntroSorter {
+
+  private final T[] arr;
+  private T pivot;
+  
+  public ArrayIntroSorter(T[] arr) {
+    this.arr = arr;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+  @Override
+  protected void setPivot(int i) {
+    pivot = arr[i];
+  }
+
+  @Override
+  protected int comparePivot(int i) {
+    return pivot.compareTo(arr[i]);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayIntroSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayMergeSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayMergeSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayMergeSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayMergeSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,63 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayMergeSorter<T extends java.lang.Comparable<? super T>> extends MergeSorter {
+
+  private final T[] arr;
+  private final T[] tmp;
+
+  public ArrayMergeSorter(T[] arr, int maxTempSlots) {
+    super(maxTempSlots);
+    this.arr = arr;
+    @SuppressWarnings("unchecked")
+    final T[] tmp = (T[]) new Comparable[maxTempSlots];
+    this.tmp = tmp;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void save(int from, int to) {
+    tmp[to] = arr[from];
+  }
+
+  @Override
+  protected void restore(int i, int slot) {
+    arr[slot] = tmp[i];
+  }
+
+  @Override
+  protected int compareSaved(int i, int j) {
+    return tmp[i].compareTo(tmp[j]);
+  }
+
+  @Override
+  protected void copy(int src, int dest) {
+    arr[dest] = arr[src];
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayMergeSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTernaryHeapSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTernaryHeapSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTernaryHeapSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTernaryHeapSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,38 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+public class ArrayTernaryHeapSorter<T extends java.lang.Comparable<? super T>> extends TernaryHeapSorter {
+
+  private final T[] arr;
+
+  public ArrayTernaryHeapSorter(T[] arr) {
+    this.arr = arr;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTernaryHeapSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native

Added: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTimSorter.java
URL: http://svn.apache.org/viewvc/commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTimSorter.java?rev=1479109&view=auto
==============================================================================
--- commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTimSorter.java (added)
+++ commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTimSorter.java Sat May  4 13:55:17 2013
@@ -0,0 +1,64 @@
+package org.apache.commons.sorting;
+
+/*
+ * 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.
+ */
+
+
+public class ArrayTimSorter<T extends java.lang.Comparable<? super T>> extends TimSorter {
+
+  private final T[] arr;
+  private final T[] tmp;
+
+  public ArrayTimSorter(T[] arr, int maxTempSlots) {
+    super(maxTempSlots);
+    this.arr = arr;
+    @SuppressWarnings("unchecked")
+    final T[] tmp = (T[]) new Comparable[maxTempSlots];
+    this.tmp = tmp;
+  }
+
+  @Override
+  protected int compare(int i, int j) {
+    return arr[i].compareTo(arr[j]);
+  }
+
+  @Override
+  protected void swap(int i, int j) {
+    swap(arr, i, j);
+  }
+
+  @Override
+  protected void copy(int src, int dest) {
+    arr[dest] = arr[src];
+  }
+
+  @Override
+  protected void saveAll(int start, int len) {
+    System.arraycopy(arr, start, tmp, 0, len);
+  }
+
+  @Override
+  protected void restore(int src, int dest) {
+    arr[dest] = tmp[src];
+  }
+
+  @Override
+  protected int compareSaved(int i, int j) {
+    return tmp[i].compareTo(arr[j]);
+  }
+
+}

Propchange: commons/sandbox/sorting/trunk/src/test/java/org/apache/commons/sorting/ArrayTimSorter.java
------------------------------------------------------------------------------
    svn:eol-style = native