# 合併排序(Merge Sort)

該排序法採用經典的分治策略(Divide and Conquer)將問題分(divide)成一些小的問題然後遞迴求解，而治(conquer)的階段則將分的階段得到的各答案修補在一起，即分而治之。

## 舉例說明
假設有一陣列 [8, 4, 5, 7, 1, 3, 6, 2]，會先將陣列每次拆分成兩組同大小的子陣列，直到每組都只有一個元素再進行排序後合併。

流程如下圖：


分的部分很好實現，就是每次都拆分成兩半，合的部分需要花點時間想一下。

## 思路

分的部分應該很好理解，所以著重講一下治(conquer)的部分。

我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，要將 [4,5,7,8] 和 [1,2,3,6] 兩個已經有序的子序列，合併為最終序列 [1,2,3,4,5,6,7,8]。

將 i 索引指向陣列第一個元素，j 索引指向 mid + 1(右子序列第一個元素)，將i 與 j 進行比較，哪個元素比較小就放到 temp 中轉陣列中存放，並且記得將索引後移，一直重複比較直到某一子序列已經遍歷結束。

來看下實現步驟：


若某一子序列已經遍歷結束但另一子序列還未遍歷結束，則會將那個子序列的剩下元素全部放進 temp 陣列中，最後將 temp 陣列 copy 回 arr 陣列。


## 程式碼實現

使用遞迴方式實現：

package Sort;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println("原序列為："+Arrays.toString(arr));
        int temp[] = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("合併排序後序列為："+Arrays.toString(arr));
    }

    // divide and conquer
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left < right) {
            int mid = (left + right) / 2;
            // 向左遞迴進行分解
            mergeSort(arr, left, mid, temp);
            // 向右遞迴進行分解
            mergeSort(arr, mid + 1, right, temp);
            // 合併
            merge(arr, left, mid, right, temp);
        }
    }

    // merge
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 初始化i, 左邊有序序列的初始索引
        int j = mid + 1; // 初始化j, 右邊有序序列的初始索引
        int t = 0; // 指向temp陣列的當前索引

        // (一) 左右子序列比大小, 將小的放到temp陣列
        while(i <= mid && j <= right) { // 左右子序列都還沒遍歷到最後時
            if(arr[i] <= arr[j]) { // 若左子序列值小於等於右子序列值，則將之放到 temp 陣列中
                temp[t] = arr[i];
                t += 1; // temp陣列索引後移
                i += 1; // 遍歷下一個
            } else { // 右子序列值小於等於左子序列值
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        // (二) 把有剩餘數據的子序列依次全部放入temp
        while(i <= mid) { // 左子序列有剩餘的元素
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }

        while(j <= right) { // 右子序列有剩餘的元素
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        // (三) 將 tmep 陣列的元素 copy 到 arr , 並不是每次都 copy 所有
        t = 0;
        int tempLeft = left; // 用於暫時遍歷 temp 陣列
        while(tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }

    }
}

output

原序列為：[8, 4, 5, 7, 1, 3, 6, 2]
合併排序後序列為：[1, 2, 3, 4, 5, 6, 7, 8]

## 速度測試

測試八十萬筆資料合併排序需要花多少時間：

public static void main(String[] args) {
        // int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
        int arr[] = new int[80000];
        for(int i = 0; i < 80000; i++) {
            arr[i] = (int)(Math.random() * 80000);
        }
        
        int temp[] = new int[arr.length];
        // System.out.println("原序列為："+Arrays.toString(arr));
        Instant startTime = Instant.now();
        mergeSort(arr, 0, arr.length - 1, temp);
        // System.out.println("合併排序後序列為："+Arrays.toString(arr));
        Instant endTime = Instant.now();
        System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }

output

共耗時：10 毫秒
共耗時：11 毫秒
共耗時：11 毫秒
共耗時：11 毫秒

10~11ms 就能對八十萬筆資料進行合併排序。

## 時間複雜度
假設今天要對一陣列使用合併排序法由小到大排序。

### 最佳：O(nlogn)
### 平均：O(nlogn)
### 最差：O(nlogn)

:::warning
T(n) = mergeSort(左子數列) + mergeSort(右子數列) + merge = T(n/2) + T(n/2) + c×n = O($nlog_2n$)
:::