//merge.c  -- Merge sort as a reference for the Lab12
// @CopyLeft by tsaiwn@csie.nctu.edu.tw
/// 再給大家一個也是很快的 sorting : 合併排序(Merge sort)
///// 但這個 sorting 演算法需要一倍的額外空間 (memory space)
// 這方法其實很簡單! 
/// 假如你有一疊考卷想要照成績排成由高到低
/// 你會怎麼做?  ==> 先分成兩疊, 交給兩個人幫忙各自排好
///// 收回來後, 兩疊是各自排好的, 你要如何"合併 ( merge)" ??
/// 眼觀兩堆, 等於每次看到兩份考卷, 把要得拿到一邊去(第三堆);
/// .. 然後, 還是看到兩堆的最上面! ... 重複上面"拿走"..
//. ..  一定會有一堆先被拿光! 再來呢? 整堆靠過去啊!
/// 把人工的做法寫成 program 就可以了! 
////// This program 故意不使用 struct (照 Lab12 規定)
// 因此, 各個重要動作都寫成 function
/// 以便處理多個 array  (這些 array 從之前 inssort.c 抄來)
/// 還有, 因為太多資料, 所以偷懶使用 Global, 不用參數傳遞
/// Space complexity: O(n)
///  就是說 Merger sort 還需要額外與原資料一樣多的空間!! 
/// 現在, 感覺沒有 struct 很難過? 開始知道 struct 的好處了吧?
/// 這程式中有些 functions 是從 sel222.c 抄寫過來的 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>  
int x[ ] = { 33, 88, 58, 92, 50, 88, 66, 68}; // 故意改為有兩個88
const int nStu = (sizeof x / sizeof x[0]);
float x2[ ] = {180.5, 172, 166.2, 170, 168, 159.5, 173, 165.3};
char x3[ ][9] = { "張三", "李嗣五", "陳火扁", "李等毀", "哈拉",
         "馬扁騙", "李博文", "宋雖委"};
// temporary memory area, 透過pointer在主程式內用 malloc 要空間
typedef char name_type[9];   // 注意寫法喔!
int *tmp;
float *tmp2;
name_type *tmp3;  // malloc 記得須要到與原 data 一樣大的空間
///////////////////// 
void copy2tmp(int k, int i);
void copyBack(int i); 
void merge(int left, int right, int m, int(*)(int, int));
void mergeSort(int left, int right, int(*comp)(int,int)) {
   int mid;
   if(left >= right) return; // nothing to do :-)
   mid = (left+right)/2;
   mergeSort(left, mid, comp);
   mergeSort(mid+1, right, comp);
   merge(left, right, mid, comp);  // 注意要把比較函數傳過去
} // mergeSort(  
void merge(int left, int right, int mid, int(*comp)(int,int)) {
   int i, r, to;
   i = to = left;
   r = mid+1;
   while((i <= mid) && (r <= right)) { // 左右都還有資料
      if(comp(i, r) <= 0) {    // a[i]<a[r] ?
         copy2tmp(to, i);  // t[to]=a[i];
         to++;  i++;
      }else{
         copy2tmp(to, r);   // t[to]=a[r];
         to++;  r++;
      }
   }// while
   while(i <= mid) {  // 左半還有嗎?
      copy2tmp(to, i);  // t[to]=a[i];
      to++; i++;
   }
   while(r <= right) {  // 右半還有嗎?
      copy2tmp(to, r);  // t[to]=a[r];
      to++; r++;
   }
   for(i=left; i < to; i++){
      copyBack(i);  // a[i] = t[i];   // copy back to a[ ]
   }
} // merge(   
////////////////////////////////////////
void printArray(int n) {
  int i;
  for(i = 0; i < n; i++) {
     fprintf(stdout, "%d %5.1f %s\n", x[i], x2[i], x3[i]);
  } // for i
} // printArray(   
///
/// 以下會把各 data 的 i-th 與 k-th 項目對調 
void copy2tmp(int k, int i) {  // ?[k] = ??[i]
   tmp[k]=x[i];
   tmp2[k]=x2[i];  // 別寫錯變數喔
   strcpy(tmp3[k], x3[i]);;;
}// copy2tmp
///  
void copyBack(int i) {  // ??[i] = ?[i]
   x[i] = tmp[i];
   x2[i] = tmp2[i];   
   strcpy(x3[i], tmp3[i]);;
}// copy2tmp   
///
////// 寫個 compare function 給 sort 用
/// 注意傳入的 i, k 是指第幾個, 不是資料本身 
int myComp(int i, int k)  {  // 注意不是直接比資料 !
   if(x[i] > x[k]) return 1;   // Ascending order
   if(x[i] < x[k]) return -1;
   return 0;
} // myComp(   
/// 再寫一個compare function, 顛倒順序 (由大到小)
int yourComp(int i, int k)  {  // 注意不是直接比資料 !
   if(x[i] > x[k]) return -1;   // Descending order
   if(x[i] < x[k]) return 1;
   return 0;
} // yourComp(   
///再一個compare function, 比 x2[ ] 內容 (身高? )
int comp22(int i, int k)  {  // 注意不是直接比資料 !
   if(x2[i] > x2[k]) return -1;   // Descending order
   if(x2[i] < x2[k]) return 1;    // 高到矮 :-)
   return 0;
} // comp22(  
/// /// ///  
int main( ) {   // 這主程式與 sel22.c 很像 !
     int i, k, nRecord;
// allocate temporary area for merge sort
   tmp = (int*)malloc( sizeof x);
   tmp2 = (float*)malloc(sizeof x2);
   tmp3 = (name_type*)malloc(sizeof x3);
///
  fprintf(stderr, "Demo Merge Sort mergeSort( )... ");
  nRecord = nStu;   //  nStu 是 Global 變數
  //
  fprintf(stdout, "\nBefore Sort\n--- ---\n");
  printArray(nRecord);  
   ///
  mergeSort(0, nRecord-1, myComp); // data in 3 global array
   ///
  fprintf(stdout, "\nAfter merge Sort\n--- --- ---\n");
  printArray(nRecord); 
  printf("Again, sort with another compare function...\n");
   /// 傳入不同的 compare function, 就可排出不同的結果!!
  mergeSort(0, nRecord-1, yourComp);
  printArray(nRecord); 
  ///
  printf("Again, again, 這次用 comp22 比身高...\n");
  mergeSort(0, nRecord-1, comp22);  // 注意  comp22 是比身高
  printArray(nRecord); 
  fprintf(stderr, "\nHit ENTER key...");
  getchar( );  return 0;
} // main(   
/******************  
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> gcc merge.c
D:\test> a.exe
Demo Merge Sort mergeSort( )...
Before Sort
--- ---
33 180.5 張三
88 172.0 李嗣五
58 166.2 陳火扁
92 170.0 李等毀
50 168.0 哈拉
88 159.5 馬扁騙
66 173.0 李博文
68 165.3 宋雖委

After merge Sort
--- --- ---
33 180.5 張三
50 168.0 哈拉
58 166.2 陳火扁
66 173.0 李博文
68 165.3 宋雖委
88 172.0 李嗣五
88 159.5 馬扁騙
92 170.0 李等毀
Again, sort with another compare function...
92 170.0 李等毀
88 172.0 李嗣五
88 159.5 馬扁騙
68 165.3 宋雖委
66 173.0 李博文
58 166.2 陳火扁
50 168.0 哈拉
33 180.5 張三
Again, again, 這次用 comp22 比身高...
33 180.5 張三
66 173.0 李博文
88 172.0 李嗣五
92 170.0 李等毀
50 168.0 哈拉
58 166.2 陳火扁
68 165.3 宋雖委
88 159.5 馬扁騙

Hit ENTER key...

********************************/