归并排序的思路是 采用分治法，将一个大的问题拆分成若干个小问题，将一个大数组 拆为多个小数组进行排序 后再进去重组。 入下图锁示

拼合2个数组的思路：因为2个数组其实都是排过序的，只要给2个数组都设置个游标可以跟简单的进行组合。如下图所示

实现代码：

void _real_merge(int arr[], int start, int mid, int end)
{
    int* temp = malloc(sizeof(int) * (end - start));
    int start1 = start;
    int start2 = mid;
    int length = 0;
    
    while(1)
    {
        //两侧都用完
        if(start1>=mid && start2 >= end)
        {
            break;
        }
        
        //有一侧的元素已经用完
        else if(start1>=mid)
        {
            temp[length++] = arr[start2];
            start2++;
        }
        else if(start2 >= end)
        {
            temp[length++] = arr[start1];
            start1++;
        }
        
        //后大
        else if(arr[start1] <= arr[start2])
        {
            temp[length++] = arr[start1];
            start1++;
        }
        
        //前大
        else if(arr[start1] > arr[start2])
        {
            temp[length++] = arr[start2];
            start2++;
        }
    }
    
    //赋值回原来数组
    for (int j = start; j<end; j++)
    {
        arr[j] = temp[j-start];
    }
    
    free(temp);
}



void sort_merge(int arr[],int start, int end)
{
    if(start == end - 1 )
    {
        return;
    }
    
    int partCount  = (end - start)/2;

    sort_merge(arr, start, start + partCount);
    sort_merge(arr, start + partCount, end);
    _real_merge(arr, start, start + partCount, end);
}

int arr[] = {8,4,5,7,1,3,6,2};        
int len= (sizeof(arr) / sizeof(int));
sort_merge(arr, 0, len);

参考文章和图片引用链接：
http://www.cnblogs.com/chengxiao/p/6194356.html