package model;

import java.util.ArrayList;
import java.util.List;

public class MergeSort {

	public List<Double> sort(List<Double> unsorted) {
		List<Double> left, right, sorted;

		if (unsorted.size() <= 1) {
			return unsorted;

		} else {
			left = unsorted.subList(0, unsorted.size()/2);
			right = unsorted.subList(unsorted.size()/2, unsorted.size());
			left = sort(left);
			right = sort(right);
		}

		sorted = merge(left, right);
		return sorted;
	}

	private List<Double> merge(List<Double> left, List<Double> right) {
		List<Double> merge = new ArrayList<Double>();
		int i = 0, j = 0;

		while(i < left.size() || j < right.size()) {

			if(i < left.size() && j < right.size()) {
				if (left.get(i).compareTo(right.get(j)) < 0) {
					merge.add(left.get(i++));
				} else {
					merge.add(right.get(j++));
				}
			} else if (i < left.size()) {
				merge.add(left.get(i++));

			} else if(j < right.size()) {
				merge.add(right.get(j++));
			}

		}

		return merge;

	}

	public static void main(String[] args) {

		List<Double> inputList = new ArrayList<Double>();
		for (int i = 0; i < 100; i++) {
			inputList.add((1 + Math.random())*(1 + Math.random()));
		}


		System.out.println("INPUT SIZE: " + inputList.size() + "\n");

		MergeSort mergeSort = new MergeSort();
		inputList = mergeSort.sort(inputList);
		System.out.println("SORTED LIST:");
		for(Double d : inputList) {
			System.out.println(d);
		}


	}

}