Merge Sort 合併排序法

tags: LeetCode sort merge sort

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

$O(nlogn)$。

---

一、步驟觀察

• 將陣列對半拆分至剩一個元素 ( 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
• Merge Sort Using C, C++, Java, and Python | What is Merge Sort and Examples of it?