Sort.java

package net.metajungle.sorting;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Sorting algorithms  
 * 
 * @author b0kaj
 *
 */
public class Sort {

    /**
     * Insert sort 
     * 
     * @param data
     */
    public static <T extends Comparable<? super T>> void insertSort(List<T> data) {
        if (data != null && data.size() > 0) {
            // iterate over the input data 
            for (int i = 0; i < data.size(); i++) {
                // item to put in place 
                T item = data.get(i);
                // find insertion location
                int j = i;
                while (j > 0 && item.compareTo(data.get(j - 1)) < 0) {
                    // use library method to swap items 
                    Collections.swap(data, j, j - 1);
                    j--; 
                }
                // insert item 
                data.set(j, item);
            }
        }
    }
    
    /**
     * Quick sort the given list 
     * 
     * @param data
     */
    public static <T extends Comparable<? super T>> void quickSort(List<T> data) {
        if (data != null && data.size() > 1) {
            quickSort(data, 0, data.size() - 1);
        }
    }
    
    /**
     * Quick sort 
     * 
     * @param data
     * @param l
     * @param r
     */
    private static <T extends Comparable<? super T>> void quickSort(List<T> data, int l, int r) {
        if (l < r) {
            // partition table 
            int p = partition(data, l, r);
            // sort left of pivot 
            quickSort(data, l, p - 1);
            // sort right of pivot 
            quickSort(data, p + 1, r);
            
        }
    }
    
    /**
     * Partition for quick sort 
     * 
     * @param data
     * @param l
     * @param r
     * @return
     */
    private static <T extends Comparable<? super T>> int partition(List<T> data, int l, int r) {
        T pivot  = data.get(r);
        int i = l;
        for (int j = l; j < r; j++) {
            if (data.get(j).compareTo(pivot) <= 0) {
                Collections.swap(data, i, j);
                i += 1;
            }
        }
        // put pivot in its place
        Collections.swap(data, i, r);
        return i;
    }

    /**
     * Merge sort 
     * 
     * @param data
     */
    public static <T extends Comparable<? super T>> void mergeSort(List<T> data) {
        if (data != null && data.size() > 1) {
            mergeSort(data, 0, data.size() - 1);
        }
    }
    
    private static <T extends Comparable<? super T>> void mergeSort(List<T> data, int l, int r) {
        // base case
        if (r - l + 1 > 1) {
            // find middle index  
            int m = ((int) (r - l) / 2) + l;
            // recursively sort two halves 
            mergeSort(data, l, m);
            mergeSort(data, m + 1, r);
            // merge sorted halves
            merge(data, m, l, r);
        }
    }
    
    /**
     * Merge two sorted parts of an array  
     * 
     * @param data
     * @param m
     * @param l
     * @param r
     */
    protected static <T extends Comparable<? super T>> void merge(List<T> data, int m, int l, int r) {
        try {
            // copy halves into temporary lists so we can write over the 
            // original data  
            List<T> left = copy(data, l, m);
            List<T> right = copy(data, m + 1, r);
            
            for (int i = l; i < r + 1; i++) {

                List<T> src = left;
                if (left.isEmpty()) {
                    src = right;
                } else if (right.isEmpty()) {
                    src = left;
                } else {
                    src = (left.get(0).compareTo(right.get(0)) <= 0) ? left : right;  
                }
                
                T value = src.remove(0);
                data.set(i, value);
            }
            
        } catch (IndexOutOfBoundsException e) {
            System.err.println("Index out of bounds: " + e.getMessage());
        }
    }
    
    /**
     * Utility to return a copy of a list  
     * 
     * @param src
     * @param from
     * @param to
     * @return
     * @throws IndexOutOfBoundsException
     */
    protected static <T> List<T> copy(List<T> src, int from, int to) throws IndexOutOfBoundsException {
        List<T> list = new ArrayList<>();
        for (int i = from; i < to + 1; i++) {
            list.add(src.get(i));
        }
        return list;
    }
}