void Merge(SeqList R，int low，int m，int high) 
 {//將兩個有序的子文件R[low..m)和R[m+1..high]歸并成一個有序的 
 //子文件R[low..high] 
 int i=low，j=m+1，p=0； //置初始值 
 RecType *R1； //R1是局部向量，若p定義為此類型指針速度更快 
 R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))； 
 if(! R1) //申請空間失敗 
 Error("Insufficient memory available!")； 
 while(i<=m&&j<=high) //兩子文件非空時取其小者輸出到R1[p]上 
 R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]； 
 while(i<=m) //若第1個子文件非空，則復制剩余記錄到R1中 
 R1[p++]=R[i++]； 
 while(j<=high) //若第2個子文件非空，則復制剩余記錄到R1中 
 R1[p++]=R[j++]； 
 for(p=0，i=low；i<=high；p++，i++) 
 R[i]=R1[p]；//歸并完成后將結果復制回R[low..high] 
 } //Merge 

void MergeSortDC(SeqList R，int low，int high) 
 {//用分治法對R[low..high]進行二路歸并排序 
 int mid； 
 if(low<high){//區(qū)間長度大于1 
  mid=(low+high)/2； //分解 
  MergeSortDC(R，low，mid); //遞歸地對R[low..mid]排序 
  MergeSortDC(R，mid+1，high)； //遞歸地對R[mid+1..high]排序 
  Merge(R，low，mid，high)； //組合，將兩個有序區(qū)歸并為一個有序區(qū) 
 } 
 }//MergeSortDC 

public class MergeSortTest { 
 
 public static void main(String[] args) { 
 int[] data = new int[] { 2, 4, 7, 5, 8, 1, 3, 6 }; 
 System.out.print("初始化：\t"); 
 print(data); 
 System.out.println(""); 
 
 mergeSort(data, 0, data.length - 1); 
  
 System.out.print("\n排序后: \t"); 
 print(data); 
 } 
 
 public static void mergeSort(int[] data, int left, int right) { 
 if (left >= right) 
  return; 
 //兩路歸并 
 // 找出中間索引 
 int center = (left + right) / 2; 
 // 對左邊數(shù)組進行遞歸 
 mergeSort(data, left, center); 
 // 對右邊數(shù)組進行遞歸 
 mergeSort(data, center + 1, right); 
 // 合并 
 merge(data, left, center, center + 1, right); 
 System.out.print("排序中:\t"); 
 print(data); 
 } 
 
 /** 
 * 將兩個數(shù)組進行歸并，歸并前面2個數(shù)組已有序，歸并后依然有序 
 * 
 * @param data 
 *  數(shù)組對象 
 * @param leftStart 
 *  左數(shù)組的第一個元素的索引 
 * @param leftEnd 
 *  左數(shù)組的最后一個元素的索引 
 * @param rightStart 
 *  右數(shù)組第一個元素的索引 
 * @param rightEnd 
 *  右數(shù)組最后一個元素的索引 
 */ 
 public static void merge(int[] data, int leftStart, int leftEnd, 
  int rightStart, int rightEnd) { 
 int i = leftStart; 
 int j = rightStart; 
 int k = 0; 
 // 臨時數(shù)組 
 int[] temp = new int[rightEnd - leftStart + 1]; //創(chuàng)建一個臨時的數(shù)組來存放臨時排序的數(shù)組 
 // 確認分割后的兩段數(shù)組是否都取到了最后一個元素 
 while (i <= leftEnd && j <= rightEnd) { 
  // 從兩個數(shù)組中取出最小的放入臨時數(shù)組 
  if (data[i] > data[j]) { 
  temp[k++] = data[j++]; 
  } else { 
  temp[k++] = data[i++]; 
  } 
 } 
 // 剩余部分依次放入臨時數(shù)組（實際上兩個while只會執(zhí)行其中一個） 
 while (i <= leftEnd) { 
  temp[k++] = data[i++]; 
 } 
 while (j <= rightEnd) { 
  temp[k++] = data[j++]; 
 } 
 k = leftStart; 
 // 將臨時數(shù)組中的內(nèi)容拷貝回原數(shù)組中 // （原left-right范圍的內(nèi)容被復制回原數(shù)組） 
 for (int element : temp) { 
  data[k++] = element; 
 } 
 } 
 
 public static void print(int[] data) { 
 for (int i = 0; i < data.length; i++) { 
  System.out.print(data[i] + "\t"); 
 } 
 System.out.println(); 
 } 
} 

初始化： 2 4 7 5 8 1 3 6 
 
排序中: 2 4 7 5 8 1 3 6 
排序中: 2 4 5 7 8 1 3 6 
排序中: 2 4 5 7 8 1 3 6 
排序中: 2 4 5 7 1 8 3 6 
排序中: 2 4 5 7 1 8 3 6 
排序中: 2 4 5 7 1 3 6 8 
排序中: 1 2 3 4 5 6 7 8 
 
排序后: 1 2 3 4 5 6 7 8