Esimerkkinä järjestysalgoritmit, missä testaan muutamaa n log n -algoritmia vastakkain.
Ne ovat merge-, quick-, heap- ja Javan oletus-sort sekä myös itseni kehittämä bitsort. Lisäksi verrokkina käytän insertionsortia O( n^2 ).
Huom! Algoritmit eivät todellakaan ole optimoituja, niiden tarkoitus on olla suhteellisen helppolukuisia oppimista varten, vaikkei niiden selitystä olekaan.
Tiedostot ja Javadocin saa osoitteesta:
http://users.utu.fi/hvkhut/koodit/sorttestbench.zip

Copyright, Henrik Huttunen

BitSorter.java
import java.util.List;

/**
 * BitSorter sorts <i>positive integers</i> very fast using bit manipulation.
 * @author Henrik Huttunen
 *
 */
public class BitSorter implements Sorter<Integer> {

        public void sort(List<? extends Integer> list) {
       
                bitSort(0, list.size()-1, list);
        }
        /**
         * bitSort sorts given list between area of [start, end].<br>
         * O( n * log k ), where n is the size of the list, and k is the biggest value in the list.
         */
        public void bitSort(int start, int end, List<? extends Integer> list)
        {
                bitSort( start, end, findHighestBit(start, end, list), list );
        }
        /**
         *
         * @param testBit Integer presentation of the bit that is used to divide integer
         * values in two seperate parts in the given area [start, end].
         */
        private void bitSort(int start, int end, int testBit, List<? extends Integer> list)
        {
            if( testBit == 0 | start >= end )
                return;   

            int last = start - 1;
            int search = end;
            boolean found = false;
                
            for( int i = start; i <= search; ++i)
            {
                         // Testing list's i:th item
                        if( !testValue( ((Integer)list.get(i)), testBit)  )
                                last = i;
                else
                {
                    found = false;
                    for( ; search > i; --search)
                    {
                        if( !testValue( ((Integer)list.get(search)), testBit) )
                        {
                            last = i;
                            // If proper search found, let's change the list's i:th and search:th places
                            ToolBox.swap(i, search, list);
                            found = true;
                            --search;
                            break; // end inner-for                     
                        }   
                    }
                    if(found == false)
                        break;
                }
            }
            bitSort( start, last, testBit >> 1, list );
            bitSort( last + 1, end, testBit >> 1, list);               
        }
        /**
         *
         * @param value Value to be tested.
         * @param testBit Tester bit.
         * @return Is testBit on (in value).
         */
        private boolean testValue(int value, int testBit)
        {
                return ( testBit & value ) > 0; 
        }
        /**
         * Finds the highest bit in the list.
         * @return The highest bit that exists in the list of integers
         */
        private int findHighestBit(int start, int end, List<? extends Integer> list)
        {
            // The highest number in list
            int maxNum = 0;
            for(int i = start; i <= end; ++i)
            {
                if( list.get(i).compareTo( maxNum ) > 0 )
                                maxNum = list.get(i).intValue();
            }
            // The highest bit needed in testing
            int x = 0;
            while(true)
            {
                if( (1<<(x+1)) <= maxNum )
                        ++x;
                else break;
            }
            return 1<<x;
        }
}

Distribution.java

/**
 * Distribution of random values.
 *
 */
public interface Distribution {
        public double getNextRandom();
}

EvenDistribution.java
import java.util.Random;
/**
 * Random numbers are scattered uniformly.
 *
 */
public class EvenDistribution implements Distribution {

        private Random random = Factory.createSeededRandom();
       
        public double getNextRandom() {
                return random.nextDouble();
        }
}
Factory.java

import java.util.List;
import java.util.Random;

/**
 * Creator of complex objects.
 *
 */
public class Factory {
        /**
         *
         * @param sorterName Name of the used Sorter.
         * @param usedTime
         * @param wasSuccess
         * @return New TestResult-object.
         */
        public static TestResult createSorterTestResult(String sorterName, long usedTime, boolean wasSuccess)
        {
                return new SorterTestResult(sorterName, usedTime, wasSuccess);
        }
        /**
         * Creates IntegerTester.
         * @param sorters Sorters that will be tested.
         * @param typeName Type of the values used in sortable list.
         * @param distributionName Used distribution.
         * @param listRandomizer List randomizer.
         */
        public static Tester createIntegerTester(List<Sorter<Integer>> sorters, String typeName, String distributionName, ListRandomizer<Integer> listRandomizer) {
                return new SorterTester<Integer>(sorters, typeName, distributionName, listRandomizer);
        }
        /**
         * Creates FloatTester.
         * @param sorters Sorters that will be tested.
         * @param typeName Type of the values used in sortable list.
         * @param distributionName Used distribution.
         * @param listRandomizer List randomizer.
         */     
        public static Tester createFloatTester(List<Sorter<Float>> sorters, String typeName, String distributionName, ListRandomizer<Float> listRandomizer) {
                return new SorterTester<Float>(sorters, typeName, distributionName, listRandomizer);
        }
        /**
         * Creates StringTester.
         * @param sorters Sorters that will be tested.
         * @param typeName Type of the values used in sortable list.
         * @param distributionName Used distribution.
         * @param listRandomizer List randomizer.
         */     
        public static Tester createStringTester(List<Sorter<String>> sorters, String typeName, String distributionName, ListRandomizer<String> listRandomizer) {
                return new SorterTester<String>(sorters, typeName, distributionName, listRandomizer);
        }
        /**
         * Creates IntegerListRandomizer.
         */
        public static ListRandomizer<Integer> createIntegerListRandomizer(int minValue, int maxValue, Distribution distribution) {
                return new IntegerListRandomizer(minValue, maxValue, distribution);
        }
        /**
         * Creates FloatListRandomizer.
         */
        public static ListRandomizer<Float> createFloatListRandomizer(float minValue, float maxValue, Distribution distribution) {
                return new FloatListRandomizer(minValue, maxValue, distribution);
        }
        /**
         * Creates StringListRandomizer.
         */     
        public static ListRandomizer<String> createStringListRandomizer(int minLength, int maxLength, Distribution distribution) {
                return new StringListRandomizer(minLength, maxLength, distribution);
        }
        /**
         * @return New Random-object with a seed generated from the current system time.
         */     
        public static Random createSeededRandom()
        {
                return new Random(System.currentTimeMillis());
        }
}
FloatListRandomizer.java
import java.util.ArrayList;
import java.util.List;

/**
 * ListRandomizer for Float-values.
 *
 */
public class FloatListRandomizer implements ListRandomizer<Float>{
        private float minValue;
        private float maxValue;
       
        Distribution distribution;
       
        /**
         * @return List of randomized float values.
         */
        public List<Float> createRandomizedList(long size)
        {
                double random;
                List<Float> list = new ArrayList<Float>();
                for(int i=0;i<size;++i)
                {
                        random = distribution.getNextRandom();
                        Float value = (float)( minValue + ToolBox.floatRemainder((float)(random*(maxValue-minValue)),maxValue-minValue));
                        assert value >= minValue & value <= maxValue : value;
                        list.add( value );
                }
                return list;
        }
        public FloatListRandomizer(float minValue, float maxValue, Distribution distribution)
        {
                this.minValue = minValue;
                this.maxValue = maxValue;
                this.distribution = distribution;
        }
}
GaussianDistribution.java
import java.util.Random;

/**
 * Randomized numbers with gaussian distribution.
 *
 */
public class GaussianDistribution implements Distribution {

        private Random random = Factory.createSeededRandom();
       
        /**
         * Returns random number with gaussian distribution.
         */
        public double getNextRandom() {
                return random.nextGaussian();
        }
}
HeapSorter.java
import java.util.List;

/**
 * Sorter that uses Heapsort-algorithm.
 *
 */
public class HeapSorter<T extends Comparable> implements Sorter<T> {

        private int heapSize;
        /**
         * Sorts list with Heapsort-algorithm.
         *  O( n log n ).
         */
        public void sort(List<? extends T> list) {
                heapSort(list);
        }
        private <T extends Comparable<T>> void heapSort(List<T> list)
        {
                buildmaxHeap(list);
                for(int i = list.size() - 1; i >= 1; --i)
                {
                        ToolBox.swap(0, i, list);
                        --heapSize;
                        maxHeapify(list, 0);
                }
        }
        private <T extends Comparable<T>> void buildmaxHeap(List<T> list)
        {
                heapSize = list.size();
                for(int i = list.size() / 2 - 1; i >= 0; --i)
                        maxHeapify(list, i);
        }

        private <T extends Comparable<T>> void maxHeapify(List<T> list, int index)
        {
                int largest;
                int left = getLeftChild(index);
                int right = getRightChild(index);

                if(left < heapSize && list.get(left).compareTo( list.get(index) ) > 0 )
                        largest = left;
                else
                        largest = index;
                if(right < heapSize && list.get(right).compareTo( list.get(largest) ) > 0 )
                        largest = right;
                if(largest != index)
                {
                        ToolBox.swap(index, largest, list);
                        maxHeapify(list, largest);
                }              
        }
        private int getLeftChild(int index){
                return 2 * index + 1;
        }
        private int getRightChild(int index){
                return 2 * index + 2;
        }
}
InsertionSorter.java
import java.util.List;

/**
 * Sorter that uses Insertionsort-algorithm.
 *
 */
public class InsertionSorter<T extends Comparable> implements Sorter<T> {

        /**
         * Sorts with Insertionsort-algorithm.
         */
        public void sort(List<? extends T> list) {
               
                for(int i=1;i<list.size();++i)
                {
                        int j = findPlaceForNextNode(i, list);
                        moveNode(i, j, list);
                }
        }
        private <T extends Comparable<T>> int findPlaceForNextNode(int i, List<T> list) {
                int j = i - 1;
                while(  j >= 0 &&
                                list.get(j).compareTo( list.get(i) ) > 0 )
                {
                        --j;
                }
                ++j;
                return j;
        }
        private <T> void moveNode(int i, int j, List<T> list)
        {
                T node = list.get(i);
                list.remove(i); // poisto ei vaikuta j:n paikkaan, sillä j <= i
                list.add(j, node);
        }
}
IntegerListRandomizer.java
import java.util.ArrayList;
import java.util.List;

/**
 * ListRandomizer for Integer-values.
 *
 */
public class IntegerListRandomizer implements ListRandomizer<Integer>{
        private int minValue;
        private int maxValue;
       
        Distribution distribution;
       
        /**
         * @return List of randomized integer values.
         */
        public List<Integer> createRandomizedList(long size)
        {
                double random;
                List<Integer> list = new ArrayList<Integer>();
               
                for(int i=0;i<size;++i)
                {
                        random = distribution.getNextRandom();

                        Integer value = (int)( minValue + ToolBox.intRemainder((int)(random*(maxValue-minValue)), maxValue-minValue));
                        assert value >= minValue & value <= maxValue : value;
                        list.add( value );
                }
                return list;
        }
        public IntegerListRandomizer(int minValue, int maxValue, Distribution distribution)
        {
                this.minValue = minValue;
                this.maxValue = maxValue;
                this.distribution = distribution;
        }
}
IntenseDistribution.java
import java.util.Random;

/**
 * Distribution that has an intense peak in it.
 *
 */
public class IntenseDistribution implements Distribution {

        private Random random = Factory.createSeededRandom();
        private double[] values;
       
        /**
         * @return random number n, 0 <= n <= 1.
         */
        public double getNextRandom() {
                double value = values[ (int)(10*random.nextDouble()) ];
                value = (value+random.nextDouble()/5) % 1.0f;
                return random.nextDouble();
        }
        public IntenseDistribution()
        {
                values = new double[]{0.1, 0.4, 0.43, 0.45, 0.49, 0.55, 0.75, 0.85, 0.9, 0.92};
        }
}
ListRandomizer.java
import java.util.List;

/**
 * Randomizer for list values.
 *
 */
public interface ListRandomizer<T extends Comparable> {
        public List<T> createRandomizedList(long size);
}
MergeSorter.java
import java.util.ArrayList;
import java.util.List;

/**
 * Sorter that uses Mergesort-algorithm.
 *
 */
public class MergeSorter<T extends Comparable> implements Sorter<T> {

        /**
         * Sorts list with mergesort-algorithm.
         * O( n log n ).
         */
        public void sort(List<? extends T> list) {
                mergeSort(0, list.size()-1, list);
        }
        private <T extends Comparable<T>> void mergeSort(int left, int right, List<T> list)
        {
                if(left < right)
                {
                        int middle = (left+right)/2;
                        mergeSort(left, middle, list);
                        mergeSort(middle+1, right, list);
                        merge(left, middle, right, list);
                }
        }
        private <T extends Comparable<T>> void merge(int left, int middle, int right, List<T> list)
        {
                List<T> leftList = new ArrayList<T>();
                List<T> rightList = new ArrayList<T>();

                int leftSideLength = middle - left + 1; // middle lasketaan mukaan vasempaan puoleen
                int rightSideLength = right - middle;
               
                for(int i=0;i<leftSideLength;++i)
                        leftList.add(list.get(left+i));
                for(int i=0;i<rightSideLength;++i)
                        rightList.add(list.get(middle+1+i));
               
                int leftCounter = 0;
                int rightCounter = 0;
               
                for(int i = left; i <= right; ++i)
                {
                        // jos oikea on jo käytetty kokonaan, voidaan heti käyttää vasen
                        // tai sitten jos vasen on, niin voidaan oikea
                        // muuten tarkistetaan, onko vasen pienempi
                        if(     rightCounter >= rightSideLength
                                || ( leftCounter < leftSideLength
                                        && leftList.get(leftCounter).compareTo( rightList.get(rightCounter)) <= 0
                                        ) )
                        {
                                list.set(i, leftList.get(leftCounter));
                                ++leftCounter;
                        }
                        else
                        {
                                list.set(i, rightList.get(rightCounter));
                                ++rightCounter;
                        }
                }
                leftList = null;
                rightList = null;
        }
}
QuickSorter.java
import java.util.List;
/**
 * Sorter that sorts list with QuickSort-algorithm (with pivot from the end of the list).
 *
 */
public class QuickSorter<T extends Comparable> implements Sorter<T> {

        /**
         * Sorts list with Quicksort.<br>
         * Average case: O( n log n ).<br>
         * Worst case: n^2.
         */     
        public void sort(List<? extends T> list) {
                quickSort(0, list.size()-1, list);
        }
        private <T extends Comparable<T>> void quickSort(int left, int right, List<T> list)
        {
                if(left < right)
                {
                        int middle = partition(left, right, list);
                       
                        quickSort(left, middle - 1, list);
                        quickSort(middle + 1, right, list);
                }
        }
        private <T extends Comparable<T>> int partition(int left, int right, List<T> list)
        {
                T pivot = list.get(right);
                int addPlace = left;

                for(int i = left; i < right; ++i)
                {
                        if( list.get(i).compareTo( pivot ) <= 0 )
                        {
                                ToolBox.swap(addPlace, i, list);
                                ++addPlace;
                        }
                }
                ToolBox.swap(addPlace, right, list);
                return addPlace;
        }
}
Sorter.java
import java.util.List;

/**
 * Sorter sorts given list.
 *
 */
public interface Sorter<T extends Comparable> {
        public void sort(List<? extends T> list);
}
SorterTestBench.java

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;

/**
 * Concrete testbench for testing different sorting algorithms with different distribution, value types and sizes.
 *
 */
public final class SorterTestBench extends TestBench{
        private final int intMinValue = 1;
        private final int intMaxValue = 1000;
        private final float floatMinValue = 1.0f;
        private final float floatMaxValue = 1000.0f;
        private final int stringMinLength = 1;
        private final int stringMaxLength = 20;
       
        private final int testRepeats = 5;
       
        private final String gaussianDistr = "Gaussian distribution";
        private final String evenDistr = "Even distribution";
        private final String intenseDistr = "Intense distribution";
       
        private List<Sorter<Integer>> integerSorters = new ArrayList<Sorter<Integer>>();
        private List<Sorter<Float>> floatSorters = new ArrayList<Sorter<Float>>();
        private List<Sorter<String>> stringSorters = new ArrayList<Sorter<String>>();
       
        private List<Tester> testers = new ArrayList<Tester>();
        private List<TestResult> testResults;
        private List<Integer> sizes = new ArrayList<Integer>();

        private Map< String, Long > testRepetitions = new HashMap<String, Long>();
       
        protected final int setTestRepeats()
        {
                return testRepeats;
        }
        protected final void setUpTestables() {
                setUpIntegerSorters();
                setUpFloatSorters();
                setUpStringSorters();
        }
        protected final void setUpTestSizes() {
                addListSize(100);
                addListSize(1000);
                addListSize(10000);
                addListSize(20000);
                addListSize(50000);
                addListSize(100000);
                addListSize(200000);
                addListSize(500000);
        }

        protected final void setUpTesters() {
                Distribution evenDistribution = new EvenDistribution();
                Distribution gaussianDistribution = new GaussianDistribution();
                Distribution intenseDistribution = new IntenseDistribution();
               
                addTester( Factory.createIntegerTester(integerSorters, "Int", evenDistr, Factory.createIntegerListRandomizer(intMinValue, intMaxValue, evenDistribution)) );
                addTester( Factory.createIntegerTester(integerSorters, "Int", gaussianDistr, Factory.createIntegerListRandomizer(intMinValue, intMaxValue, gaussianDistribution)) );
                addTester( Factory.createIntegerTester(integerSorters, "Int", intenseDistr, Factory.createIntegerListRandomizer(intMinValue, intMaxValue, intenseDistribution)) );
                addTester( Factory.createFloatTester(floatSorters, "Float", evenDistr, Factory.createFloatListRandomizer(floatMinValue, floatMaxValue, evenDistribution)) );
                addTester( Factory.createFloatTester(floatSorters, "Float", gaussianDistr, Factory.createFloatListRandomizer(floatMinValue, floatMaxValue, gaussianDistribution)) );
                addTester( Factory.createFloatTester(floatSorters, "Float", intenseDistr, Factory.createFloatListRandomizer(floatMinValue, floatMaxValue, intenseDistribution)) );
                addTester( Factory.createStringTester(stringSorters, "String", evenDistr, Factory.createStringListRandomizer(stringMinLength, stringMaxLength, evenDistribution)) );
                addTester( Factory.createStringTester(stringSorters, "String", gaussianDistr, Factory.createStringListRandomizer(stringMinLength, stringMaxLength, evenDistribution)) );
                addTester( Factory.createStringTester(stringSorters, "String", intenseDistr, Factory.createStringListRandomizer(stringMinLength, stringMaxLength, intenseDistribution)) );
        }
        private void setUpIntegerSorters() {
                //integerSorters.add(new InsertionSorter<Integer>());
                integerSorters.add(new QuickSorter<Integer>());
                integerSorters.add(new MergeSorter<Integer>());
                integerSorters.add(new BitSorter());
                integerSorters.add(new SunQuickSorter<Integer>());
                integerSorters.add(new HeapSorter<Integer>());
        }
        private void setUpFloatSorters() {
//            floatSorters.add(new InsertionSorter<Float>());
                floatSorters.add(new QuickSorter<Float>());
                floatSorters.add(new MergeSorter<Float>());
                floatSorters.add(new SunQuickSorter<Float>());
                floatSorters.add(new HeapSorter<Float>());
        }
        private void setUpStringSorters() {
//            stringSorters.add(new InsertionSorter<String>());
                stringSorters.add(new QuickSorter<String>());
                stringSorters.add(new MergeSorter<String>());
                stringSorters.add(new SunQuickSorter<String>());
                stringSorters.add(new HeapSorter<String>());
        }       
}
SorterTester.java
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * SorterTester handles a test case of different Sorters with given type.
 *
 *
*/
public class SorterTester<T extends Comparable<T>> implements Tester<T> {

        private List<Sorter<T>> sorters;
        private String distributionName;
        private String typeName;
        private ListRandomizer<T> listRandomizer;
        private List<T> randomizedList;
        private List<List<TestResult>> testResults = new ArrayList<List<TestResult>>();
       
        private Timer timer = new Timer();
        /**
         *
         * @param sorters Sorter-objects whose performace will be tested.
         * @param typeName Name of the type that is used in the test. e.g. Integer.
         * @param distributionName Name of the distribution.
         * @param listRandomizer For making randomized lists.
         */
        public SorterTester(List<Sorter<T>> sorters, String typeName, String distributionName, ListRandomizer<T> listRandomizer)
        {
                this.sorters = sorters;
                this.typeName = typeName;
                this.distributionName = distributionName;
               
                this.listRandomizer = listRandomizer;
        }
        /**
         * test runs testcase with given <b>listSize</b> and repeats test <b>testRepeats</b> times with different list each time.
         */
        public List<TestResult> test(int listSize, int testRepeats) {
               
                setUpResultList();
                for(int i=0; i < testRepeats; ++i)
                {       
                        randomizeList(listSize);
                        Iterator<Sorter<T>> it = sorters.iterator();
                        int sorterIndex = 0;
                        while( it.hasNext() )
                        {
                                List<T> sortableList = ToolBox.makeACopy( randomizedList );
                                TestResult testResult = testSorter(timer, sortableList, it.next());
                                sortableList = null;
                                addResult(testResult, sorterIndex);
                                ++sorterIndex;
                        }
                }
                randomizedList = null;
                List<TestResult> results = getResults(testRepeats);
                return results;
        }
        /**
         *  testRepeats > 0
         */
        private List<TestResult> getResults(int testRepeats)
        {
                if( testRepeats == 0 )
                        throw new RuntimeException("testRepeats must be > 0.");
                List<TestResult> results = new ArrayList<TestResult>();
                for(List<TestResult> tests: testResults)
                {
                        String sorterName = tests.get(0).getTestableName();
                        long totalTime = 0;
                        boolean wasSuccess = true;
                        for(TestResult result: tests)
                        {
                                totalTime += result.getUsedTime();
                                wasSuccess = wasSuccess & result.isValidResult(); // jos yksikin testi epäonnistui
                        }
                        long averageTime = totalTime / testRepeats;
                        results.add(Factory.createSorterTestResult(sorterName, averageTime, wasSuccess ));
                }
                return results;
        }
        private void addResult(TestResult testResult, int sorterIndex)
        {
                testResults.get(sorterIndex).add(testResult);
        }
        private void setUpResultList()
        {
                testResults.clear();
                for(int i=0;i<sorters.size();++i)
                        testResults.add(new ArrayList<TestResult>());
        }
        private void randomizeList(int listSize)
        {
                randomizedList = listRandomizer.createRandomizedList(listSize);  
        }
        private TestResult testSorter(Timer timer, List<T> sortableList, Sorter<?> sorter) {
                timer.restart();
                sorter.sort( sortableList );
                long usedTime = timer.getPassedTime();
               
                boolean success = ToolBox.isSortedAscending( sortableList );
                return Factory.createSorterTestResult(sorter.getClass().getName(), usedTime, success);
        }
        /**
         * @return Type of the values and the distribution that are used in the test.
         */
        public String getInfo()
        {
                return "Value types: " + typeName + " [#] " + "Distribution: " + distributionName;
        }
}
SorterTestResult.java
/**
 * Test results.
 *
 */
public class SorterTestResult implements TestResult {

        private String sorterName;
        private long usedTime;
        private boolean success;
       
        /**
         * @return Name of the used Sorter.
         */
        public String getTestableName() {
                return sorterName;
        }
        /**
         * @return Spent time that Sorter used in the test.
         */
        public long getUsedTime() {
                return usedTime;
        }
        /**
         * @return Was sorting done correctly.
         */
        public boolean isValidResult()
        {
                return success;
        }
        public SorterTestResult(String sorterName, long usedTime, boolean success)
        {
                this.sorterName = sorterName;
                this.usedTime = usedTime;
                this.success = success;
        }
}
StringListRandomizer.java
import java.util.ArrayList;
import java.util.List;

/**
 * List randomizer for String-values.
 *
 */
public class StringListRandomizer implements ListRandomizer<String>{

        private int minLength;
        private int maxLength;
       
        Distribution distribution;
       
        /**
         * @return Randomized list that consists of Strings.
         */
        public List<String> createRandomizedList(long size)
        {
                double random;
                StringBuffer word;
                List<String> list = new ArrayList<String>();
               
                for(int i=0;i<size;++i)
                {
                        random = distribution.getNextRandom();
                        Integer length = (int)( minLength + ToolBox.intRemainder((int)(random*(maxLength-minLength)),maxLength-minLength));
                        word = new StringBuffer();
                       
                        for(int j=0;j<length;++j)
                        {
                                random = distribution.getNextRandom();
                                char c = (char)((int)'A' + (random * 60)%60);
                                word.append(c);
                        }
                        list.add( word.toString() );
                }
                return list;
        }
        public StringListRandomizer(int minLength, int maxLength, Distribution distribution)
        {
                this.minLength = minLength;
                this.maxLength = maxLength;
                this.distribution = distribution;
        }
}
SunQuickSorter.java
import java.util.List;

/**
 * Sorter that uses Sun's default sorter (enhanced quicksort).
 *
 */
public class SunQuickSorter<T extends Comparable> implements Sorter<T>{

        /**
         * Sorts list with Sun'n default sort.
         * O( n log n ).
         */
        public void sort(List<? extends T> list) {
                java.util.Collections.sort(list);
        }
}
TestBench.java
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;

/**
 * Testbench framework for testing different algorithms with different (size) input.
 *
 */
public abstract class TestBench{
        private int testRepeats;
               
        private List<Tester> testers = new ArrayList<Tester>();
        private List<Integer> sizes = new ArrayList<Integer>();
        private List<TestResult> testResults;   

        private Map< String, Long > testRepetitions = new HashMap<String, Long>();
       
        /**
         * Executes the tests.
         *
         */
        public final void run()
        {
                setUp();
                System.out.println("Test results are average of " + testRepeats + " repetition.");
               
                for(Integer size: sizes)
                {
                        for(Tester<?> tester: testers)
                        {
                                testResults = tester.test(size, testRepeats);
       
                                System.out.println("\t|-----------------------------------------------------------");
                                System.out.println("\t| size: "+size);
                                System.out.println("\t| "+tester.getInfo());
                               
                                for(TestResult result: testResults)
                                {
                                        System.out.println("\t| \t"+result.getTestableName() + ": " + (result.isValidResult() ? "succeeded" : "failed") + " in " + ((double)result.getUsedTime())/1000 + " seconds.");
                                }                     
                        }
                }
        }
        private void setUp()
        {
                testRepeats = setTestRepeats();
                setUpTestables();              
                setUpTesters();
                setUpTestSizes();
        }
        /**
         * Set how many times a test case will be repeated for better accuracy.
         * @return Amount of repetitions in a test case.
         */
        protected abstract int setTestRepeats();
        /**
         * Add a list size to be tested.
         * @param size A List size in a test case.
         */
        protected final void addListSize(int size) {
                sizes.add(size);
        }
        /**
         * Add a Tester.
         */
        protected final void addTester(Tester tester){
                testers.add(tester);
        }
        /**
         * Prepare testables.
         */
        protected abstract void setUpTestables();
        /**
         * Add list sizes to be tested using <i>addListSize(int size)</i>.
         */
        protected abstract void setUpTestSizes();
        /**
         * Add testers that will be executed using <i>addTester(Tester tester)</i>.
         */
        protected abstract void setUpTesters();

        public static void main(String[] args)
        {
                System.out.println("TestBench started.");
                new SorterTestBench().run();
                System.out.println("TestBench completed.");
        }
}
Tester.java
import java.util.List;

/**
 * Test case for testing performance of different algorithms.
 */
public interface Tester<T extends Comparable<T>> {
        /**
         * Executes the tests.
         * @param listSize Size of the list.
         * @param testRepeats How many times tests are repeated with given size.
         * @return TestResults in list.
         */
        public List<TestResult> test(int listSize, int testRepeats);
        /**
         *
         * @return Information about the test case.
         */
        public String getInfo();
}

TestResult.java

/**
 * Test results for single test case.
 *
 */
public interface TestResult {
        /**
         *
         * @return Name of the testable unit.
         */
        public String getTestableName();
        /**
         *
         * @return Time used executing.
         */
        public long getUsedTime();
        /**
         *
         * @return Was executing done correctly.
         */
        public boolean isValidRe