[hardwired]

Code:

import java.util.*;

public class MergeSortRx {
    public <T extends Comparable<? super T>> void mergesort(List<T> toSort) {
        if (toSort.size()<=1){
            /*Do Nothing*/
        }
        else{
            int low = 0;
            int high = toSort.size()-1;
            print(toSort, "original collection");
            sort(toSort, low, high);
        }
    }

    private <T extends Comparable<? super T>> void sort(List<T> toSort,
                                                        int low, int high) {
        if(low == high){
            /*Do Nothing*/
            return;
        }
        else{
            int middle = (high+low)/2;
            sort(toSort, low, middle);
            sort(toSort, middle+1, high);
            merge(toSort, low, middle, high);
        }
    }

    private <T extends Comparable<? super T>> void merge(List<T> toSort,
                               int low, int middle, int high) {
        int loCount = low;
        int midCount = middle;
        int hiCount = middle+1;

        while(loCount <= midCount && hiCount <= high) {
            T lo = toSort.get(loCount);
            T hi = toSort.get(hiCount);
            int compare = lo.compareTo(hi);
            if(compare < 0) {    // lo < hi
                loCount++;
            } else {             // lo >= hi
                T temp = hi;
                for(int j = hiCount-1; j >= loCount; j--)
                    toSort.set(j+1, toSort.get(j));
                toSort.set(loCount, temp);
                loCount++;
                midCount++;
                hiCount++;
            }
        }
    }

    private <T> void print(List<T> list, String title) {
        System.out.println(title);
        for(int j = 0; j < list.size(); j++) {
            System.out.print(list.get(j));
            if(j < list.size()-1)
                System.out.print(", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MergeSortRx ms = new MergeSortRx();
        int[] ints = { 5, 7, 9, 3, 16, 12, 4 };
        List<Integer> list = new ArrayList<Integer>();
        for(int j = 0; j < ints.length; j++)
            list.add(Integer.valueOf(ints[j]));
        ms.mergesort(list);
        ms.print(list, "after sorting");
        System.out.println("--------------");
        String[] s = "bdoaplvjertmxn".split("(?<=[\\w])");
        List<String> sList = Arrays.asList(s);
        ms.mergesort(sList);
        ms.print(sList, "after sorting");
    }
}