# Merge Sort 合併排序法
###### tags: `LeetCode` `sort` `merge sort`

:::info
:pushpin: 合併排序法採用了分治法 ( Divide and Conquer ) 概念，將陣列對半拆開，拆到小陣列只剩一個元素，拆開之後，排序再合併。它的時間複雜度是 $O(nlogn)$。
:::
---

{%youtube JSceec-wEyw %}

## 一、步驟觀察

* 將陣列對半拆分至剩一個元素 ( Divide，並使用到 ==Recursive 的概念== )
* 針對相鄰兩個陣列做完比較後，完成排序與合併 ( Conquer )


( 圖片來源 wiki )

## 二、實際操作
### 使用哪種資料結構：Array
* 將 left 和 right 作為陣列兩端的索引
* 初始化 left l 等於 0 ; right r 等於 arr.length-1
* 如果 r > l，可以拆分的情況
* 找出中間點，將陣列對半拆開
* 呼叫 mergeSort( ) 處理左邊陣列
* 呼叫 mergeSort( ) 處理右邊陣列
* 呼叫 merge( )，排序並合併兩個陣列

**邏輯：**

  arr <- an array of integers
  let len be the length of arr
  let left l be the beginning index of array
  let right r be the end index of the array
  
  func mergeSort(arr, l, r):
    if r > l then
      mid = l + (r-l)/2
      meargeSort(arr, l, mid)
      meargeSort(arr, mid+1, r)
      merge()
    end if
  end func
  

**程式碼實作：**

debugger
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r)
{
    var n1 = m - l + 1;
    var n2 = r - m;
  
    // Create temp arrays
    var L = new Array(n1); 
    var R = new Array(n2);
  
    // Copy data to temp arrays L[] and R[]
    for (var i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (var j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
  
    // Merge the temp arrays back into arr[l..r]
  
    // Initial index of first subarray
    var i = 0;
  
    // Initial index of second subarray
    var j = 0;
  
    // Initial index of merged subarray
    var k = l;
  
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    // Copy the remaining elements of
    // L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
  
    // Copy the remaining elements of
    // R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
  
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
function mergeSort(arr,l, r){
    if(l>=r){
        return;//returns recursively
    }
    var m =l+ parseInt((r-l)/2);
    mergeSort(arr,l,m);
    mergeSort(arr,m+1,r);
    merge(arr,l,m,r);
}

var arr = [ 12, 11, 13, 5, 6, 7 ];
mergeSort(arr, 0, arr.length - 1);

<!-- ## 四、優化改善
內容 -->

## 三、時間複雜度 Big O
* Merge Sort is θ(nLogn) in all 3 cases ( worst, average and best ) as merge sort always divides the array into two halves and takes linear time to merge two halves.

### Drawbacks of Merge Sort
* Slower comparative to the other sort algorithms for smaller tasks.
* Merge sort algorithm ==requires an additional memory space of 0(n) for the temporary array==.
* It goes through the whole process even if the array is sorted.

---

參考資料：
* https://ithelp.ithome.com.tw/articles/10241640
* [Merge Sort - GeeksforGeeks](https://www.geeksforgeeks.org/merge-sort/)
* [Merge Sort Using C, C++, Java, and Python | What is Merge Sort and Examples of it?](https://www.mygreatlearning.com/blog/merge-sort/#t2)