歸并排序：二路歸并排序
此算法采用自頂向下的歸并排序算法，算法形式簡潔，首先設排序的目前區間為a[low...high]
具體步驟：
分解：将目前區間一分為二，即求分裂點。
求解：遞歸地對兩個子區間a[low...middle]和a[middle+1...high]進行歸并排序
組合：将已排序的兩個子區間a[low...middle]和a[middle+1...high]歸并為一個有序的區間r[low...high]
遞歸總結條件：子區間長度為1（一個記錄本身就是有序的）
算法的代碼實作：
#include <stdio.h>
#include <stdlib.h>
void merge(int a[], int temp[], int l_pos, int m_pos, int r_end)
{
int i = 0;
int left_pos = l_pos;
int l_end = m_pos;
int r_pos = m_pos + 1;
while(l_pos <= l_end && r_pos <= r_end)
{
if(a[l_pos] < a[r_pos])
{
temp[i++] = a[l_pos++];
}
else
temp[i++] = a[r_pos++];
}
while(l_pos <= l_end)
temp[i++] = a[l_pos++];
while(r_pos <= r_end)
temp[i++] = a[r_pos++];
/*copy from temp to a*/
for(i = left_pos; i <= r_end; i++)
a[i] = temp[i-left_pos];
}
void _m_sort(int a[], int temp[], int low, int high)
int m_pos = 0;
if(low >= high)
return ;
m_pos = (high + low) / 2;
_m_sort(a, temp, low, m_pos);
_m_sort(a, temp, m_pos+1, high);
merge(a, temp, low, m_pos, high);
void m_sort(int a[], int size)
int *temp = NULL;
temp = (int *)malloc(size*sizeof(int));
if(temp != NULL)
_m_sort(a, temp, 0, size-1);
free(temp);
int main(void)
int a[] = {4,3,5,1,2};
m_sort(a, 5);
for(i = 0; i < 5; i++)
printf("%d\n", a[i]);
return 0;