演算法類型
divide and conquer, 排序演算法演算法目的
利用比較 key value 來將資料做排序演算法描述
merge sort 的核心觀念是將大筆資料切割成很多小筆資料做排序，接著利用已經排序好的小筆資料合併成排序好的大筆資料。merge sort 的概觀流程圖如下:
分割步驟相信大家應該沒有什麼問題，就是一次將資料切一半。比較需要解釋的應該是合併步驟，以下舉例說明合併步驟如何進行，假設要合併 A 和 B 兩個已排序好的數列，如下圖:
現在我們將兩個箭頭各指著 A 數列和 B 數列的第一個元素，如下圖:
將箭頭指到的數字做比較，把比較小的數字複製到另外一個 C 數列，並且將指向比較小的數字的箭頭往前移一格，如下圖:
繼續重複剛剛的動作，如下圖:
繼續重複這個動作直到有其中一個箭頭超出數列的範圍為止，如下圖:
現在 B 數列的箭頭已經超出範圍了，所以我們剩下要做的事情就只是把 A 數列箭頭開始以後的數字全部複製到 C 數列就可以了，如下圖:
這樣 C 數列就是一個合併完成的數列了。
最壞情況時間複雜度分析
設總資料量為 n, 分析單位為比較次數依據此演算法的最壞情況，我們可以列出以下遞迴式:
T(n) = 2T(n / 2) + n - 1
T(1) = 0
根據 master theorem，可以求出此演算法為 O(nlgn) 的演算法
程式實作
C
#include <stdio.h>
void mergeSort(int *, int, int);
void merge(int *, int, int, int);
int main() {
int arr[8] = {4, 6, 1, 9, 5, 3, 0, 2};
int dataNum = 8;
int i;
printf("before sorting: ");
for (i=0; i<dataNum; i++)
printf("%d " , arr[i]);
printf("\n");
mergeSort(arr, 0, dataNum - 1);
printf("after sorting: ");
for (i=0; i<dataNum; i++)
printf("%d " , arr[i]);
printf("\n");
return 0;
}
void mergeSort(int *arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
void merge(int *arr, int low, int mid, int high) {
int leftIndex = low;
int rightIndex = mid + 1;
int tempArrLength = high - low + 1;
int tempArr[tempArrLength];
int tempIndex = 0;
while (leftIndex <= mid && rightIndex <= high) {
if (arr[leftIndex] <= arr[rightIndex]) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
}
else {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
}
tempIndex++;
}
if (leftIndex > mid) {
while (rightIndex <= high) {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
tempIndex++;
}
}
else {
while (leftIndex <= mid) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
tempIndex++;
}
}
leftIndex = low;
for (tempIndex=0; tempIndex<tempArrLength; tempIndex++) {
arr[leftIndex] = tempArr[tempIndex];
leftIndex++;
}
}
Java
public class MergeSort {
public static void main(String[] args) {
int[] arr = {4, 6, 1, 9, 5, 3, 0, 2};
System.out.print("before sorting: ");
for (int num: arr)
System.out.printf("%d " , num);
System.out.println();
mergeSort(arr, 0, arr.length - 1);
System.out.print("after sorting: ");
for (int num: arr)
System.out.printf("%d " , num);
System.out.println();
}
private static void mergeSort(int[] arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int leftIndex = low;
int rightIndex = mid + 1;
int[] tempArr = new int[high - low + 1];
int tempIndex = 0;
while (leftIndex <= mid && rightIndex <= high) {
if (arr[leftIndex] <= arr[rightIndex]) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
}
else {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
}
tempIndex++;
}
if (leftIndex > mid) {
while (rightIndex <= high) {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
tempIndex++;
}
}
else {
while (leftIndex <= mid) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
tempIndex++;
}
}
leftIndex = low;
for (int temp: tempArr) {
arr[leftIndex] = temp;
leftIndex++;
}
}
}
Python
def merge(arr, low, mid, high):
leftIndex = low
rightIndex = mid + 1
tempArr = []
while leftIndex <= mid and rightIndex <= high:
if arr[leftIndex] <= arr[rightIndex]:
tempArr.append(arr[leftIndex])
leftIndex += 1
else:
tempArr.append(arr[rightIndex])
rightIndex += 1
if leftIndex > mid:
while rightIndex <= high:
tempArr.append(arr[rightIndex])
rightIndex += 1
else:
while leftIndex <= mid:
tempArr.append(arr[leftIndex])
leftIndex += 1
leftIndex = low
for temp in tempArr:
arr[leftIndex] = temp
leftIndex += 1
def mergeSort(arr, low, high):
if low < high:
mid = (low + high) / 2
mergeSort(arr, low, mid)
mergeSort(arr, mid + 1, high)
merge(arr, low, mid, high)
arr = [4, 6, 1, 9, 5, 3, 0, 2]
print "before sorting:",
for num in arr:
print "%d" % (num),
print ""
mergeSort(arr, 0, len(arr) - 1)
print "after sorting:",
for num in arr:
print "%d" % (num),
print ""
![\begin{figure}
\centering
\setlength{\unitlength}{0.0125in} %
\begin{picture}
(2...
...raisebox{0pt}[0pt][0pt]{$\bullet
\bullet \bullet$ }}}
\end{picture}
\end{figure}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tZp95Plgi0yRJn34YMsox2duXdngASvO_d43klNUdYsQINNq4C050GdstSuLInqOg4xfv0rElNzA4lux0HSui6mOtBgSXxHmP2rNPMeWyrcpA2EBY=s0-d)
where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.
dollars thus earning a profit of 6.4 percent.
) that can be purchased with one unit of the currency of country 1.
line of the conversion table (country i). The first integer in the sequence is the country from which the profiting sequence starts. This integer also ends the sequence.
(length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.
such that each box 
nests in box 
( 
.
) nests in a box E = ( 
) if there is some rearrangement of the 
such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).
of 
such that ( 
) ``fits'' in ( 
for all 
.
line in the sequence ( 
) gives the measurements for the