插入归并

归并排序的时间复杂度为O(nlgn)，空间复杂度为O(n)；

但是一般来讲，基于从单个记录开始两两归并的排序并不是特别提倡，一种比较常用的改进就是结合插入排序，即先利用插入排序获得较长的有序子序列，然后再两两归并（改进后的归并亦是稳定的，因为插入排序是稳定的）。之所以这样改进是有原因的：尽管插入排序的最坏情况是O(n^2)，看起来大于归并的最坏情况O(nlgn)，但通常情况下，由于插入排序的常数因子使得它在n比较小的情况下能运行的更快一些，因此，归并时，当子问题足够小时，采用插入排序是比较合适的。

复杂度分析

下面分析下插入归并排序最坏情况下的复杂度：假设整个序列长度为n，当子序列长度为k时，采取插入排序策略，这样一共有n/k个子序列。

子序列完成排序复杂度：最坏情况下，n/k个子序列完成排序的时间复杂度为O(nk)。证明：每个子序列完成插入排序复杂度为O(k^2)，一共n/k个子序列，故为O(nk)。

子序列完成合并复杂度：最坏情况下，合并两个子序列的时间复杂度为O(n)，一共有n/k个子序列，两两合并，共需要lg(n/k)步的合并，所以这些子序列完成合并的复杂度为O(nlg(n/k))。

所以改进后的插入归并排序的最坏情况的复杂度为O(nk+nlg(n/k))，这里k的最大取值不能超过lgn，显然如果k大于lgn，复杂度就不是与归并一个级别了，也就是说假设一个1000长度的数组，采用插入策略排序子序列时，子序列的最大长度不能超过10。

/*
二路归并排序 
*/

void Merge(int* array,int low,int middle,int high)
{
	int* temp = new int[sizeof(int)*(high-low+1)];
	int first = low;
	int second = middle+1;
	int i=0;
	while(first<=middle&&second<=high)
	{
		if(array[first] < array[second])
		{
			temp[i++] = array[first++];
		}
		else
		{
			temp[i++] = array[second++];
		}
	}	
	while(first<=middle)
	{
		temp[i++] = array[first++];
	}
	while(second<=high)
	{
		temp[i++] = array[second++];
	}
	memcpy(array+low,temp,sizeof(int)*(high-low+1));
	delete [] temp;
}

void MergeSort(int* array,int begin,int end)
{
	//cout<<sizeof(array)<<endl;
	if((end-begin) >0)
	{
		int mid = begin + (end-begin)/2;
		MergeSort(array,begin,mid);
		MergeSort(array,mid+1,end);
		Merge(array,begin,mid,end);
	
	}
	
}
 /* 改进的归并算法：插入归并*  先通过插入排序得到较长的有序串，然后归并*  即，当分解的数组长度小于一定值时，不再分解，改用插入排序*/ #define INSERT_BOUND 5 void InsertSort(int arr[], int beg, int end){    for(int i = beg+1; i <= end; ++i)    {        int temp = arr[i];        int j = i - 1;        while(j >= beg && arr[j] > temp)        {            arr[j+1] = arr[j--];        }        arr[j+1] = temp;    }} void Insert_MergeSort(int arr[], int beg, int end, int temp_arr[]){    if(end - beg + 1 <= INSERT_BOUND)    {        InsertSort(arr,beg,end);    }else    {        int mid = (beg + end) / 2;        Insert_MergeSort(arr, beg, mid, temp_arr);        Insert_MergeSort(arr, mid+1, end, temp_arr);        Merge(arr, beg, mid, end, temp_arr);    }}

原地归并

我们说归并排序相对于快排来讲，它需要O(n)的额外空间，这一度成为归并的缺点，不过好在归并排序也可以进行原地排序，只使用O(1)的额外空间。原地归并排序所利用的核心思想便是“反转内存”的变体，即“交换两段相邻内存块”，对于反转内存的相关文章，曾在文章“关于反转字符串(Reverse Words)的思考及三种解法”中对一道面试题做了分析。这一思想用到的地方很多，在《编程珠玑》中被称为“手摇算法”。通过手摇算法的交换内存的思想来进行原地归并又有不少变种，我们举例分析一种比较常见的情况，不同的方法还有基于二分查找的方法来确定交换的内存块，在《计算机编程艺术》中也有不同的思路提供，感兴趣见本文参考资料。

下面举例说明一种原地归并排序的思想。

我们知道，无论是基于单个记录的两两归并，还是利用插入排序先得到较长的子序列然后归并，在算法合并的过程中，我们都是在合并“两个相邻的有序子序列”。

在了解原地归并的思想之前，先回忆一下一般的归并算法，先是将有序子序列分别放入临时数组，然后设置两个指针依次从两个子序列的开始寻找最小元素放入归并数组中；那么原地归并的思想亦是如此，就是归并时要保证指针之前的数字始终是两个子序列中最小的那些元素。文字叙述多了无用，见示例图解，一看就明白。

假设我们现在有两个有序子序列如图a，进行原地合并的图解示例如图b开始

如图b，首先第一个子序列的值与第二个子序列的第一个值20比较，如果序列一的值小于20，则指针i向后移，直到找到比20大的值，即指针i移动到30；经过b，我们知道指针i之前的值一定是两个子序列中最小的块。

如图c，先用一个临时指针记录j的位置，然后用第二个子序列的值与序列一i所指的值30比较，如果序列二的值小于30，则j后移，直到找到比30大的值，即j移动到55的下标；

如图d，经过图c的过程，我们知道数组块 [index, j) 中的值一定是全部都小于指针i所指的值30，即数组块 [index, j) 中的值全部小于数组块 [i, index) 中的值，为了满足原地归并的原则：始终保证指针i之前的元素为两个序列中最小的那些元素，即i之前为已经归并好的元素。我们交换这两块数组的内存块，交换后i移动相应的步数，这个“步数”实际就是该步归并好的数值个数，即数组块[index, j)的个数。从而得到图e如下：

重复上述的过程，如图f，相当于图b的过程，直到最后，这就是原地归并的一种实现思想，具体代码如下。

void Revere(int* array,int begin,int end)
{
	int temp;
	while(begin <end)
	{
		temp = array[begin];
		array[begin] = array[end];
		array[end]=temp;
		begin++;
		end--;
	}
}
/*
array 为有旋转的数组   
begin 数组的开始位置
middle 为后半段的开始 
end 为后半段开始 
*/
void Rotate_right(int* array,int begin,int middle,int end)
{
	Revere(array,begin,middle);
	Revere(array,middle+1,end);
	Revere(array,begin,end); 
} 

void Merge_second(int* array,int begin,int end)
{
	int middle = begin + (end-begin)/2+1;
	int i = begin;
	int index;
	while(middle <= end && i<middle)
	{
		while(array[i]<=array[middle] && i<middle)
		{
			i++;
		}
		index = middle;
		while(middle <=end && array[middle]<=array[i])
		{
			middle++;
		}
		Rotate_right(array,i,index-1,middle-1);
		i+=(middle-index);
	}
} 

void Inplace_MergeSort(int arr[], int beg, int end)
{
    if(beg < end)
    {
        int mid = (beg + end) / 2;
        Inplace_MergeSort(arr, beg, mid);
        Inplace_MergeSort(arr, mid+1, end);
        Merge_second(arr, beg, end);
    }
}

假如一个数组内有两段有序的序列 那么如何合并这两个有序的序列 可以使用

问题描述：
数组al[0,mid-1]和al[mid,num-1]是各自有序的，对数组al[0,num-1]的两个子有序段进行merge，
得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注：al[i]元素是支持‘<‘运算符的。

/*
思路： 将同一个数组中两段有序序列合并为一个 可以使用插入的排序方式，
将后半部分的元素插入到前半部分内 对后半部分的每一个元素 都在前半部分
找到合适的位置 然后插入  这就需要将前半部分的元素进行后移一个位置 
*/

void Merge(int* array,int begin,int end)
{
	int middle = begin +(end-begin)/2+1;
	 
	int i=begin;
	int temp;
	while(middle <=end)
	{
		temp = array[middle];
		if(array[i] < array[middle])
		{
			i++;
		}	
		else
		{
			int index = middle;
			while(index != i)
			{
				array[index] = array[index-1];
				index--;
			}
			array[i++] = temp;
			middle++;
		}
	} 
}

参考：http://www.ahathinking.com/archives/103.html

二路归并 && 插入归并 && 原地归并