import java.util.Arrays;

public class MergeSort {
	
	private void merge(int[] valores, int inicio, int meio, int fim) {
		int[] vetorTemp = new int[valores.length];
		
		// Copia todos os elementos, do inicio ao fim, no vetor temporário
		for (int i = inicio; i <= fim; i++) {
			vetorTemp[i] = valores[i];
		}

		// Percorre os dois vetores lógicos e vai copiando o menor dos valores
		int i = inicio;
		int j = meio + 1;
		int k = inicio;
		while (i <= meio && j <= fim) {
			if (vetorTemp[i] <= vetorTemp[j]) {
				valores[k] = vetorTemp[i];
				i++;
			} else {
				valores[k] = vetorTemp[j];
				j++;
			}
			k++;
		}

		// Copia o restante dos elementos
		while (i <= meio) {
			valores[k] = vetorTemp[i];
			k++;
			i++;
		}
	}
	
	private void mergesort(int[] valores, int inicio, int fim) {
		if (inicio < fim) {
			int meio = (inicio + fim) / 2;
			mergesort(valores, inicio, meio);
			mergesort(valores, meio + 1, fim);
			merge(valores, inicio, meio, fim);
		}
	}
	
	public static void main( String ... args){
		
		int[] valores = {10, 7, 14, 16, 2, 8, 4, 1};
		MergeSort sort = new MergeSort();
		sort.mergesort(valores, 0, valores.length-1 );
		
		System.out.println( Arrays.toString(valores) );
		
	}

}
