package sorting;

import java.util.Comparator;

public class MergeSort extends Sort {
    public static <E> void Sort(E[] array, Comparator<E> c) {
        sort(array, 0, array.length - 1, c, (E[]) new Object[array.length]);

    }

    private static <E> void sort(E[] array, int i, int j, Comparator<E> c,
            E[] aux) {
        if (i == j)
            return;
        sort(array, i, (i + j) / 2, c, aux);
        sort(array, (i + j) / 2+1, j, c, aux);
        merge(array, i, (i + j) / 2 , (i + j) / 2+1, j, c, aux);
    }

    private static <E> void merge(E[] array, int s1, int e1, int s2, int e2,
            Comparator<E> c, E[] aux) {
        int i=s1;
        int j=s2;
        int x=0;
        while(i<=e1&&j<=e2)
        {
            if(less(array[i],array[j],c))
            {
                aux[x++]=array[i++];
            }else{
                aux[x++]=array[j++];
            }
        }
        while(i<=e1)
        {
            aux[x++]=array[i++];
        }
        while(j<=e2)
        {
            aux[x++]=array[j++];
        }

        for(x=0;x<=j-i;x++)
            array[s1++]=aux[x];
    }
}