merge

package algorithms.sorting.merge;

import java.util.ArrayList;

import static algorithms.sorting.Template.less;

public class Merge{

    public static <T extends Comparable<T>> void merge(T[] a, int lo, int mid, int hi)
    {
        T[] aux = (T[]) new Object[a.length] ;
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++)
            aux[k] = a[k];
        for (int k = lo; k <= hi; k++)
        {
            if      (j > mid)             a[k] = a[j++];
            else if (j > hi)              a[k] = a[i++];
            else if (less(aux[j], a[i]))  a[k] = a[j++];
            else                          a[k] = a[i++];

        }

    }

    public static <T extends Comparable<T>> void sort(T[] a)
    {
        sort(a, 0, a.length-1);
    }
    public static <T extends Comparable<T>> void sort(T[] a, int lo, int hi)
    {
        if (hi <= lo) return;
        int mid = lo + (hi-lo)/2;
        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }