Natural-Merge-Sort Util

Often it is neccessary to sort an array (or an arraylist) of objects related to an specific value. That value might vary, so I wrote a simple utility for quick and easy use of an very efficient sorting-algorithm.
The utility uses the natural-merge-sort algorithm (see Wikipedia). It’s an advanced version of the merge-sort algorithm, that “merges” to sorted lists into a bigger one, and continues until just one list, the final sorted one, is left. Natural-merge-sort uses randomly pre-sorted little lists from the initial array to speed-up the whole process, instead of recursively breaking up the initial list into one-object-lists. It doens’t work in-place (it creates a new list instead of changing index of objects from the origin list).
It uses Java-generics. You can download the Util-class here.

To sort a list, your Objects need to extend the Sort.SortItem.class that provides the neccessary methods. It holds one abstract method that you need to override; it should return the value of the object, which is used for “rating” this object. For example when you want to sort a list of “Spoons” by length, you need to return the length value. Here’s an example class of a sortable object:

public class Spoon extends Sort.SortItem { 
    public final int LENGTH;
    * Default constructor
    public Spoon(int l) {
        this.LENGTH = l;
    public double getRelatedValue() {
        return LENGTH;

Then for sorting an arraylist of spoons, do the following:

ArrayList<Spoon> list; //your initial list
ArrayList<Spoon> sorted = Sort.sort(list, Sort.SortMode.ASCENDING); //the sorted list

You don’t need to pass generic type arguments, the compiler does that for you automaticly. The only thing important is, that you initial list is type of ArrayList<T extends Sort.SortItem>. That means you can only sort objects which extend the SortItem-class. The second parameter for the sorting-method is the sorting-mode. There are two modes available: Sort.SortMode.ASCENDING and Sort.SortMode.DESCENDING. They both use the same algorithm, but the descending-mode inverts the whole list at the end, that means it’s a little slower. But with a little knowledge you can just swap the operators in the algorithm and make it sort descending by default.