merge

package sorting.divideAndConquer;

import sorting.AbstractSorting;

/**
 * Merge sort is based on the divide-and-conquer paradigm. The algorithm
 * consists of recursively dividing the unsorted list in the middle, sorting
 * each sublist, and then merging them into one single sorted list. Notice that
 * if the list has length == 1, it is already sorted.
 */
public class MergeSort<T extends Comparable<T>> extends AbstractSorting<T> {

    @Override
    public void sort(T[] array, int leftIndex, int rightIndex) {
        if(leftIndex >= 0 && rightIndex < array.length && leftIndex < array.length && rightIndex >= 0 && leftIndex != rightIndex) {

            T aux[] = (T[]) new Comparable[leftIndex + rightIndex + 7];
            int mid = (leftIndex + rightIndex)/2;
            sort(array, leftIndex, mid);
            sort(array, mid+1, rightIndex);

            int i = leftIndex, j = mid+1, x = 0;
            for(;i <= mid && j <= rightIndex; x++) {
                if(array[i].compareTo(array[j]) <= 0) {
                    aux[x] = array[i++];
                }else {
                    aux[x] = array[j++];
                }
            }


            while(i <= mid) {
                aux[x++] = array[i++];
            }

            while(j <= rightIndex) {
                aux[x++] = array[j++];
            }

            for(i = leftIndex, j = 0; i <= rightIndex; i++, j++) array[i] = aux[j];
        }
    }
}