插入排序，归并排序

ALG.java

package test.algorithm;

import java.util.Arrays;

/**
 * from wiki http://zh.wikipedia.org/wiki/插入排序
 *  http://zh.wikipedia.org/wiki/归并排序
**/
public class ALG {

    /**
     * @param args
     */
    public static void main(String[] args) {
            Comparable[] c = {1,5,3,0,9,8};  
            System.out.println("before sort: " + Arrays.asList(c));
            insertionSort(c);
            System.out.println("after sort: " + Arrays.asList(c));
            System.out.println("=====================================");
            Comparable[] d = {1,5,3,0,9,8};  
            System.out.println("before sort: " + Arrays.asList(d));
            mergeSort(d);
            System.out.println("after sort: " + Arrays.asList(d));
    }

    public static void insertionSort(Comparable<Object>[] data) {
        InsertionSort.sort(data);  
    }
    
    public static <T extends Comparable<? super T>> void mergeSort(T[] data) {
        MergeSort.sort(data);
    }
}

class InsertionSort {
    public static void sort(Comparable<Object>[] data) {
        for (int index=1; index<data.length; index++) {
            Comparable<Object> key = data[index];
            int pos = index;
            // shift larger values to the right
            while ( pos > 0 && data[pos-1].compareTo(key) > 0 ) {
                data[pos] = data[pos-1];
                pos--;
            }
            data[pos] = key;
        }
    }
}

class MergeSort {
    
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void sort(T[] arr) {
        T[] tmpArr = (T[]) new Comparable[arr.length];
        sort(arr, tmpArr, 0, arr.length - 1);
    }
    
    private static <T extends Comparable<? super T>> void sort(T[] arr, T[] tmpArr, int start, int end) { 
        if (start < end) {
            int mid = (start + end) / 2; 
            System.out.printf("sort (%d-%d, %d-%d) %s\n", start, mid, mid + 1, end, Arrays.asList(arr));
            sort(arr, tmpArr, start, mid);
            sort(arr, tmpArr, mid + 1, end);
            merge(arr, tmpArr, start, mid + 1, end);
            System.out.printf("merge (%d-%d, %d-%d) %s\n", start, mid, mid + 1, end, Arrays.asList(arr));
        }
    }
    
    private static <T extends Comparable<? super T>> void merge(T[] arr, T[] tmpArr, int lPos, int rPos, int rEnd) {
        int lEnd = rPos - 1;
        int tPos = lPos;
        int leftTmp = lPos;
        
        while (lPos <= lEnd && rPos <= rEnd) {
            if (arr[lPos].compareTo(arr[rPos]) <= 0) {
                tmpArr[tPos++] = arr[lPos++];
            } else {
                tmpArr[tPos++] = arr[rPos++];
            }
        }
        
        //copy the rest element of the left half subarray
        while (lPos <= lEnd) {
            tmpArr[tPos++] = arr[lPos++];
        }
        
        //copy the rest element of the right half subarray.(only one loop will be execute)
        while (rPos <= rEnd) {
            tmpArr[tPos++] = arr[rPos++];
        }
        
        //copy the tmpArr back cause we need to change the arr array items.
        for (; rEnd >= leftTmp; rEnd--) {
            arr[rEnd] = tmpArr[rEnd];
        }
        
    }
    
    
}

before sort: [1, 5, 3, 0, 9, 8]
after sort: [0, 1, 3, 5, 8, 9]
before sort: [1, 5, 3, 0, 9, 8]
sort (0-2, 3-5) [1, 5, 3, 0, 9, 8]
sort (0-1, 2-2) [1, 5, 3, 0, 9, 8]
sort (0-0, 1-1) [1, 5, 3, 0, 9, 8]
merge (0-0, 1-1) [1, 5, 3, 0, 9, 8]
merge (0-1, 2-2) [1, 3, 5, 0, 9, 8]
sort (3-4, 5-5) [1, 3, 5, 0, 9, 8]
sort (3-3, 4-4) [1, 3, 5, 0, 9, 8]
merge (3-3, 4-4) [1, 3, 5, 0, 9, 8]
merge (3-4, 5-5) [1, 3, 5, 0, 8, 9]
merge (0-2, 3-5) [0, 1, 3, 5, 8, 9]
after sort: [0, 1, 3, 5, 8, 9]