合併排序法

說明：

• 1. 將陣列等分成 2 群，【 左群 】 及 【 右群 】 。

  2. 分別排序【 左群 】 及 【 右群 】 。

  3. 合併排序後【 左群 】 及 【 右群 】 。

  4. 遞迴呼叫分群 (1) 直至群個數剩下 1 或 2 個元素為止開始排序 。

原始碼：

def SwapValues(myArray, i, j): myTempVale = myArray[i] myArray[i] = myArray[j] myArray[j] = myTempVale def MergeSortCombine(myLeftResultArray, myRightResultArray): myLeftResultArraySize = len(myLeftResultArray) myRightResultArraySize = len(myRightResultArray) myResultArraySize = myLeftResultArraySize + myRightResultArraySize myResultArray = [-1] * myResultArraySize i = 0 j = 0 for myPos in xrange(0, myResultArraySize): if (i < myLeftResultArraySize) and (j < myRightResultArraySize): if myLeftResultArray[i] > myRightResultArray[j]: myResultArray[myPos] = myRightResultArray[j] j = j + 1 else: myResultArray[myPos] = myLeftResultArray[i] i = i + 1 else: if (i >= myLeftResultArraySize) and (j < myRightResultArraySize): myResultArray[myPos] = myRightResultArray[j] j = j + 1 if (j >= myRightResultArraySize) and (i < myLeftResultArraySize): myResultArray[myPos] = myLeftResultArray[i] i = i + 1 return myResultArray def MergeSort(myArray): myResultArray = [] arraySize = len(myArray) if arraySize==0: return myResultArray if arraySize==1: myResultArray.append(myArray[0]) return myResultArray if arraySize==2: if myArray[0] > myArray[1]: SwapValues(myArray, 0, 1) myResultArray.append(myArray[0]) myResultArray.append(myArray[1]) return myResultArray leftArraySize = arraySize // 2 if arraySize % 2==0: rightArraySize = leftArraySize else: rightArraySize = leftArraySize + 1 myLeftArray = myArray[0:leftArraySize] myRightArray = myArray[leftArraySize:] myLeftResultArray = MergeSort(myLeftArray) myRightResultArray = MergeSort(myRightArray) myResultArray = MergeSortCombine(myLeftResultArray, myRightResultArray) return myResultArray if __name__ == "__main__": myArray = [11, 99, 22, 88, 33, 77, 44, 66, 55] print(MergeSort(myArray))