Merge sort.java

import java.util.Collections;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Scanner;

public class MyMergeSort {
	
	
	static LinkedList divide (LinkedList list) {
		
		
		if (list.size()<2)
			return null;
		
		LinkedList left = new LinkedList();
		LinkedList right = new LinkedList();
		
		int middle = list.size()/2;

		for (int i = 0; i < middle; i++) {
			left.add(list.get(i));
		}
		for(int i = middle; i < list.size(); i++) {
			right.add(list.get(i));
		}
		
		divide(left);
		divide(right);
		LinkedList<Double> sortList = new LinkedList();

		return merge(left, right ,sortList);
	}
	
	
	static LinkedList merge(LinkedList<Double> left, LinkedList<Double> right,LinkedList<Double> sortList) {
		while(!left.isEmpty() || !right.isEmpty()) {
			
			if(!left.isEmpty()) {
				
				double min = left.get(0);
				int minIndex = 0;
				boolean minIfInRightList = false;
			
				for (int i = 0; i<right.size(); i++) {
					if(right.get(i)< min) {
						minIfInRightList = true;
						min = right.get(i);
						minIndex = i;
					}
				}
				
				if(minIfInRightList == true) {
					sortList.add(right.remove(minIndex));
				}else {
					sortList.add(left.remove(0));
				}
			
			}else {
				int minIndex = 0;
				double min = right.get(minIndex);
				
				for (int i = 1; i<right.size(); i++) {
					if(right.get(i)< min) {
						
						min = right.get(i);
						minIndex = i;
					}
				}
				sortList.add(right.remove(minIndex));
			
			}
		}
		
		for(double data: sortList) {
			System.out.print(data+",");
		}
		
		System.out.println();
		System.out.println();
		
		return sortList;
	}

	public static void main(String[] args) {
		
		LinkedList<Double> list = new LinkedList();
		
		Scanner sc = new Scanner(System.in);
		System.out.println("請輸入欲加入的長度:");
		int listlong=0;
	
		try {
			listlong = sc.nextInt();
		}
		catch(InputMismatchException e) {
			System.out.println("輸入格式錯誤:");
		}
		
		for(int i=0; i < listlong; i++ ) {
			try {
				double s1 = sc.nextDouble();
				list.add(s1);
			}
			catch(InputMismatchException e) {
				System.out.println("輸入格式錯誤:");
			}	
		}
		
		LinkedList printlist = divide(list);
			for(int i = 0; i < printlist.size(); i++) {
				System.out.print(printlist.get(i));
				System.out.print(",");
			}
	
	}

}