// TestMergeSort.java ปรับปรุง : 2548-06-08 ()
// เคล็ด : แยกครึ่ง และแยกเป็น biary tree แล้วก็หยิบสมาชิกแต่ละถึง มาจัดเรียงทีละตัว
// โปรแกรมสำหรับ จัดเรียงข้อมูล แบบ Merge ซึ่งเหมาะกับ External Sort
// แหล่งอ้างอิง 
//   http://www.thaiall.com/class
//   http://ww3.algorithmdesign.net/handouts/MergeSort.pdf
//   http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
//   http://www.cp.eng.chula.ac.th/%7Eu45dtn/mergesort/mergesort.htm (มีแต่ source กับ awt)
//   http://www.java2s.com/ExampleCode/Collections-Data-Structure/Sort-Search.htm
// ปัญหาที่อาจพบ 
//   ถ้า compile ทุกโปรแกรม แล้ว run ทีละโปรแกรม จะพบปัญหา SortingProcess ซ้ำกัน
//   แต่ถ้า compile และ run ทีละโปรแกรม จะไม่พบปัญหา เพราะปัญหาเกิดจาก SortingProcess ซ้ำกับในโปรแกรมอื่น
//
import java.lang.*;
class SortingProcess {
  int temp,elems=0; 
  Comparable ar[] = new Comparable[100];
  public void insert(Comparable value) { 
    ar[elems] = value;
    elems++;
  }  
  public void printresult(String txt) {
    System.out.print(txt);
    for(int i=0;i<elems;i++) {
      System.out.print(" " + ar[i]);
    }
    System.out.println();
  }
  public void MergeSort() {
    Comparable[] temp = new Comparable[elems];
    MergeSort(temp, 0, elems-1);
  }  
  private void MergeSort(Comparable[] temp, int left, int right) {
    if(left < right) {
      int mid = (left + right) / 2; 
      MergeSort(temp, left, mid); 
      MergeSort(temp, mid+1, right); 
      merge(temp, left, mid+1, right);
    }
  }
  private void merge(Comparable[] temp, int left, int right, int rightEnd) {
    int leftEnd = right - 1;
    int pos = left;
    int items = rightEnd - left + 1;
    while(left <= leftEnd && right <= rightEnd)
      if(ar[left].compareTo(ar[right]) < 0)
        temp[pos++] = ar[left++];
      else
        temp[pos++] = ar[right++];
    while(left <= leftEnd)
      temp[pos++] = ar[left++];
    while(right <= rightEnd)
      temp[pos++] = ar[right++];
    for(int i = 0; i < items; i++, rightEnd--)
      ar[rightEnd] = temp[rightEnd];
  }
}
class TestMergeSort {
  public static void main(String[] args) {
    System.out.println("Merge Sort");
    SortingProcess arr = new SortingProcess();
    arr.insert(new Integer(51));
    arr.insert(new Integer(46));
    arr.insert(new Integer(14));
    arr.insert(new Integer(35));
    arr.insert(new Integer(22));
    arr.printresult("Before :");
    arr.MergeSort();
    arr.printresult("After  :");
  }
}