歸併排序
歸併排序歸併操作
歸併操作(merge)，也叫歸併算法，指的是將兩個已經排序的序列合併成一個序列的操作。
算法描述
歸併操作的工作原理如下：
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
設定兩個指針，最初位置為別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置重複步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接複製到合併序列尾
示例代碼
以下示例代碼實現了歸併操作。array【】是元素序列，其中從索引p開始到q位置，按照升序排列，同時，從(q+1)到r也已經按照升序排列，merge()函式將把這兩個已經排序好的子序列合併成一個排序序列。結果放到array中。/**
* 0 <= p <= q < r, subarray array【p..q】 and array【q+1..r】 are already sorted.
* the merge() function merges the two sub-arrays into one sorted array.
*/
static void merge(int array【】, int p, int q, int r)
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = (int*)malloc((r-p)*sizeof(int));
begin1= p; end1 = q;
begin2 = q+1;end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2))
{
if(array【begin1】<array【begin2】)
{
temp【k】 = array【begin1】;begin1++;
}
else
{
temp【k】 = array【begin2】;begin2++;
}
k++;
}
while(begin1<end1)
{
temp【k++】 = array【begin1++】;
}
while(begin2<end2)
{
temp【k++】 = array【begin2++】;
}
for (i = 0; i < (r - p); i++)
array【p+i】 = temp;
free(temp);
}
歸併排序
歸併排序具體工作原理如下（假設序列共有n個元素）：
將序列每相鄰兩個數字進行歸併操作（merge)，形成floor(n/2)個序列，排序後每個序列包含兩個元素
將上述序列再次歸併，形成floor(n/4)個序列，每個序列包含四個元素
重複步驟2，直到所有元素排序完畢
示例代碼
示例代碼為C語言，輸入參數中，需要排序的數組為array【】,起始索引為first，終止索引為last。調用完成後，array【】中從first到last處於升序排列。
voidmerge_sort(intarray【】,unsignedintfirst,unsignedintlast)
{
intmid=0;
if(first<last)
{
mid=(first+last)/2;
merge_sort(array,first,mid);
merge_sort(array,mid+1,last);
merge(array,first,mid,last);
}
}
算法複雜度
比較操作的次數介於(nlogn)/2和nlogn-n+1。賦值操作的次數是(2nlogn)。歸併算法的空間複雜度為：Θ(n)
