package model;

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

public class MergeSort {

	public List<Double> sort(List<Double> list) {
		List<Double> left, right, result;

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

		} else if(list.size() == 2){
			left = new ArrayList<Double>();
			left.add(list.get(0));
			right = new ArrayList<Double>();
			right.add(list.get(1));

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

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

	private List<Double> merge(List<Double> left, List<Double> right) {
		List<Double> merge = new ArrayList<Double>();
		while(left.size() > 0 || right.size() > 0) {
			if(left.size() > 0 && right.size() > 0) {
				if(left.get(0) < right.get(0)) {
					merge.add(left.get(0));
					left.remove(0);
				} else {
					merge.add(right.get(0));
					right.remove(0);
				}
			} else if (left.size() > 0) {
				merge.add(left.get(0));
				left.remove(0);
			} else if (right.size() > 0) {
				merge.add(right.get(0));
				right.remove(0);
			}
		}
		return merge;

	}

	public static void main(String[] args) {

		List<Double> inputList = new ArrayList<Double>();
		inputList.add(Double.parseDouble("3"));
		inputList.add(Double.parseDouble("3.1415"));
		inputList.add(Double.parseDouble("4000.15"));
		inputList.add(Double.parseDouble("31337"));
		inputList.add(Double.parseDouble("455.455"));
		inputList.add(Double.parseDouble("666.6666666"));
		inputList.add(Double.parseDouble("6"));
//		inputList.add(Double.parseDouble("6"));
//		inputList.add(Double.parseDouble("8"));
//		inputList.add(Double.parseDouble("10"));
		inputList.add(Double.parseDouble("0.0"));


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

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


	}

}