package algoritmProgUppg1;

import java.nio.file.Files;
import java.nio.file.Paths;

public class MergeSort {

	public static void mergeSort(int[] a, int lo, int hi) {
		int mid;
		if (hi > lo) {
			mid = lo+ (hi-lo) / 2;
			mergeSort(a, lo, mid);
			mergeSort(a, mid+1, hi);
			merge(a, lo, mid, hi);
		} else {
			return;
		}
	}

	public static void merge(int[] a, int lo, int mid, int hi) {
		int[] aux = new int[a.length];

		for (int i=0; i < a.length; i++) {
			aux[i] = a[i];
		}

		int i = lo;
		int j = mid + 1;

		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = aux[j++];
			}
			else if (j > hi) {
				a[k] = aux[i++];
			}
			else if (aux[i] < aux[j]) {
				a[k] = aux[i++];
			} else {
				a[k] = aux[j++];
			}
		}
	}

	// Checks if the first n element of a are in sorted order.
	private static boolean isSorted(int[] a, int lo, int hi) {
		int flaws = 0;
		for (int i = lo+1; i <= hi; i++) {
			if (a[i] < a[i-1]) {
				if (flaws++ >= 10) {
					System.out.println("...");
					break;
				}
				System.out.println("a["+i+"] = "+a[i]+", a["+(i-1)+"] = "+a[i+1]);
			}
		}
		return flaws == 0;
	}

	static int[] readIntfile(String filename) throws Exception {
		// Read file into a byte array, and then combine every group of four bytes to an int. (Not
		// the standard way, but it works!)
		byte[] bytes = Files.readAllBytes(Paths.get(filename));
		int[] ints = new int[bytes.length/4];
		for (int i = 0; i < ints.length; i++) {
			for (int j = 0; j < 4; j++) { ints[i] += (bytes[i*4+j] & 255) << (3-j)*8; }
		}
		return ints;
	}

	public static void main(String[] args) throws Exception {
//		int[] test = {38, 27, 43, 3, 9, 82, 10, 0, -5, 13, 999};
				int[] data = readIntfile("src/smallints");
				int N = data.length;
//		int N = test.length;

		long before = System.currentTimeMillis();
		mergeSort(data, 0, N-1);
		long after = System.currentTimeMillis();

		System.out.println((after-before)/1000);
		if (N <= 1000) {
			for (int i = 0; i < data.length; i++) { System.out.print(data[i]+" "); }
			System.out.print("\n");
		}
	}
}