[演算法(Algorithm)] 合併排序法(Merge Sort)

合併排序法(歸併排序法)的概念
- 將2個已排序的陣列合併，只需要N次比對的線性時間(Linear Time)
  - 比對次數最多為：左子數列長度 + 右子數列長度 - 1
- 將數列分成左、右子數列，分別對其作排序及合併
合併排序作法：
- 將數列對分成左子數列、右子數列
- 分別對左子數列、右子數列作上一個步驟遞迴(Recursive)
  - 直到左子數列、右子數列被分割成只剩一個元素為止
  - 將僅剩的一個元素作為遞迴的結果回傳
- 對回傳的左子數列、右子數列依大小排列合併
- 將合併的結果作為遞迴的結果回傳
合併作法：：將左子數列及右子數列依大小合併成一個新的數列
- 若左子數列的數值都已填到新的數列將右子數列中未填過的最小值填入新數列
- 若右子數列的數值都已填到新的數列將左子數列中未填過的最小值填入新數列
- 將左子數列及右子數列中，未填過的最小值填到新的數列
需執行⌈log ₂n⌉回合
時間複雜度(Time Complexity)
- Best Case：Ο(n log n)
- Worst Case：Ο(n log n)
- Average Case：Ο(n log n)
  - T(n) = MergeSort(左子數列) + MergeSort(右子數列) + Merge
    = T(n/2) + T(n/2) + c×n = O(n log₂n)
空間複雜度(Space Complexity)：Ο(n)
- 需要暫時性的暫列存放每回合Merge後的結果
穩定性(Stable/Unstable)：穩定(Stable)
動畫:

速度：
Demo:

演算法

// Top-Down	
/* 將leftData與rightData依大小順序合併 */
var merge = function(leftData, rightData){
    var sortedData = new Array();
    var leftIndex = 0, rightIndex = 0;
    
    // 一一比對leftData和rightData每個元素的大小
    // 將較小者依序填入sortedData
    for(var i = 0; i < leftData.length + rightData.length; i++){
        
        //如果leftData已填完, 就填入rightData的資料
        if(leftIndex == leftData.length)         
            sortedData.push(rightData[rightIndex++]);
        
        //如果rightData已填完, 就填入leftData的資料
        else if( rightIndex == rightData.length) 
            sortedData.push(leftData[leftIndex++]);
        
        // 如果leftData < rightData,則填入leftData的資料   
        else if(leftData[leftIndex] < rightData[rightIndex])  
            sortedData.push(leftData[leftIndex++]);
        
        // 如果rightData < leftData,則填入leftData的資料
        else			
            sortedData.push(rightData[rightIndex++]);
    }
    return sortedData;
};

var mergeSort = function(data){	
    if(data.length > 1) {    // 如果資料超過1筆		
        var leftData = new Array(), rightData = new Array();
        var middle = parseInt(data.length/2);
		
        // 將資料分割成左右子串列
        for(var i = 0; i < middle; i++)  
            leftData[i] = data[i];
        for(var j = middle; j < data.length; j++)		
            rightData[j-middle] = data[j];			
		
        leftData = mergeSort(leftData);    // 對左子串列作合併排序
        rightData = mergeSort(rightData);  // 對右子串列作合併排序
        return merge(leftData, rightData); // 將左右子串列作完合併的結果合併
    }
    return data;    // 如果資料只有1筆,直接回傳
};

//執行
var result = mergeSort(data);

//Bottom-Up
var min = function(m, n){
    return (m < n) ? m : n;
};

var merge = function(data, left, middle, end, tmp){
    var leftPtr = left;
    var rightPtr = middle;
    var j = left;
    while(j < end) {
        tmp[j++] = (leftPtr < middle 
                    && (rightPtr >= end || data[leftPtr] <= data[rightPtr])) 
                   ? data[leftPtr++] 
                   : data[rightPtr++];		
    }
    for(var i = left; i < end; i++)
        data[i] = tmp[i];
};
	
var mergeSort = function(data){
    var tmp = new Array();
    var length = data.length;
    for(var width = 1; width < length; width = 2*width){	//2,4,8,16		
        for(var i = 0; i < length; i = i+2*width){
            merge(data, i, min(i+width, length), min(i+2*width, length), tmp); 
        }
    }
};

// Iterative 
var mergeSort = function(data){
    var i, leftMin, leftMax, rightMin, rightMax, next;
    var tmp = new Array();
	
    for(var i = 1; i < data.length; i *= 2){
        for(leftMin = 0; leftMin < data.length - i; leftMin = rightMax){
            rightMin = leftMax = leftMin + i;
            rightMax = leftMax + i;
            if(rightMax > data.length)
                rightMax = data.length;
            next = 0;
            while(leftMin < leftMax && rightMin < rightMax)
                tmp[next++] = data[leftMin] > data[rightMin] 
                              ? data[rightMin++] 
                              : data[leftMin++];
            while(leftMin < leftMax)
                data[--rightMin] = data[--leftMax];
            while(next > 0 )
                data[--rightMin] = tmp[--next];			
		}
	}
};