排序算法--归并排序

#include<iostream>

using namespace std;

void print(int *arr,int length)
{
 for(int i = 0;i < length;i++)
 {
  cout<<arr[i]<<"\t";
 }
 cout<<"\n";
}

void merge(int *arr1,int *arr2,int i,int m,int n)
{
 for(int j = m + 1,k = i; i <=m && j <= n;k++)
 {
  if(arr1[i] < arr1[j])
  {
   arr2[k] = arr1[i++];
  }
  else
  {
   arr2[k] = arr1[j++];
  }
 }

 if(i <= m)
 {
  for(;i <= m;i++)
  {
   arr2[k++] = arr1[i];
  }
 }

 if(j <= n)
 {
  for(;j <= n;j++)
  {
   arr2[k++] = arr1[j];
  }
 }
}

void MergeSort(int sourceArr[], int targetArr[],int startIndex, int endIndex)
{   
 int midIndex;    
 int tempArr[4];    
 if(startIndex == endIndex)    
 {        
  targetArr[startIndex] = sourceArr[startIndex];    
 }    
 else   
 {        
  midIndex = (startIndex + endIndex)/2;        
  MergeSort(sourceArr, tempArr,startIndex, midIndex);        
  MergeSort(sourceArr, tempArr, midIndex+1, endIndex);        
  merge(tempArr, targetArr,startIndex, midIndex, endIndex);    
 }
}

int main()
{
 int arr1[4] = {8,5,7,4};
 int arr2[4];
 int size = sizeof(arr1)/sizeof(int);
 cout<<"排序前数组元素为："<<endl;
 print(arr1,size);
 
 MergeSort(arr1,arr2,0,size-1);
 cout<<"排序后数组元素为："<<endl;
 print(arr2,size);
 return 0;
}

原文：http://www.cnblogs.com/WangYinlong/p/3549114.html