package sort;
import java.util.*;import java.io.*;
public class MergeSort{ public static int times; public void mergeSort (Comparable [] data,int min,int max) { if (min==max) return; int pivot = (min+max)/2; mergeSort(data,min,pivot); mergeSort(data,pivot+1,max); merge(data,min,pivot,max); } private void merge(Comparable [] data,int min,int pivot ,int max) { Comparable temp[] ; int left ; int right; int size = max-min+1; temp = new Comparable[size]; for (int i=0; i<size; i++) { temp[i] = data[min+i]; } // merge the 2 sorted lists left = 0; right = pivot-min+1; for (int i=0;i<size;i++) { times++; if(right<=max-min) if (left<=pivot-min) if (temp[left].compareTo(temp[right])>0) data[i+min] = temp[right++]; else data[i+min] = temp[left++]; else data[i+min] = temp[right++]; else data[i+min] = temp[left++]; } } public static void main(String [] args) throws IOException { String inString ; StringTokenizer tokenizer; Integer [] elements; MergeSort ms = new MergeSort(); BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); System.out.println("Please input the size ( size>0 ): "); inString = in.readLine(); elements = new Integer[Integer.parseInt(inString)]; System.out.println("Enter the numbers of elements :(gap it with Key_space or Key_tab) "); inString = in.readLine(); tokenizer = new StringTokenizer(inString); for (int i =0; i<elements.length && tokenizer.hasMoreTokens();i++) { elements[i] = Integer.parseInt(tokenizer.nextToken()); } long startTime = System.currentTimeMillis(); ms.mergeSort(elements,0,elements.length-1); System.out.println("after sorted :"); for (int i=0;i<elements.length;i++) { System.out.println(elements[i]); } System.out.println("take time = "+(System.currentTimeMillis()-startTime)); System.out.println("size : "+elements.length+" , cursory times : "+times); }}
