排序算法4：合并排序

合并排序介绍

合并排序基于分而治之。

以下是基本步骤，之后我们将研究实现。

划分： 将数组分成两半。如果数组具有n个元素，则在第一级将其除以n / 2。然后将那些2数组再次除以2。继续直到只有单个元素。

征服： 递归对数组的左部分和数组的右部分排序。

结合： 将数组的左侧部分和数组的右侧部分合并为单个排序的数组。

下图是对数组[40、10、5、20、15、34、7、9]执行的合并排序的图像

划分：

因为我们有8个元素，所以中间元素将是5。因此，我们将数组分为2部分。如果您观察代码，则对数组进行划分后，将递归调用子数组的左侧部分，直到其被排序为止，然后再调用子数组的右侧部分。

请记住，我们将跟踪算法的工作方式。

首先，它将如下分割数组的左部分：

再说一次，我们有4个元素，中间元素是2，再次除以数组的左部分，如下所示：

同样，我们有2个元素将其划分，如下所示：

完成左侧部分后，我们向上移动1级并将右侧部分划分如下：

现在左侧和右侧部分已经划分，我们将它们组合成一个排序的数组，如下所示：

现在，我们如下所示拆分子数组的右侧部分：

再次我们如下分割数组：

然后我们将它们合并如下：

然后，我们对整个子数组进行排序和合并，如下所示：

同样，我们对右子数组也做同样的事情。在为右子数组执行操作时，我们再次选择右子数组的左侧部分并执行类似的操作。完整的递归树如下所示：

下面我提到了如何进行分而治之的步骤。

执行合并排序的步骤：

要执行合并排序，我们需要3个元素：

1.要排序的数组。
2.最低索引。
3.最高索引。

我们需要最低和最高索引来计算索引的中间部分，并将数组分为两部分，以后可以合并。

算法MergeSort（array，low，high）

If (low < high)
	 mid <- (low + high) /2	  			// To divide the array into left and right array.
	MergeSort(array, low, mid) 			// Sort left array.
	MergeSort(array, mid + 1, high) 		// Sort right array.
	MergeSortedArray (a, low, mid, high) 	// Merge the sorted left and right array

使用C语言合并排序实现：

#include<stdio.h>

void print_array(int array[], int length)
{
	int index = 0;

	printf("The sorted array is \n");

	for(index = 0 ; index < length ; index++)
	{
		printf("%d\n",array[index] );
	}
}

void  merge_sorted_array( int array[], int low, int mid_index, int high)
{
	int temp_array [100];

	int i = low;
	int j = mid_index + 1 ;
	int k = low;

	while (i <= mid_index && j <= high)
	{
		if(array[i] < array [j])
		{
			temp_array [k] = array[i];
			i++;
			k++;
		}
		else
		{
			temp_array [k] = array[j];
			j++;
			k++;
		}
	}

	//copy the left part of the array to temp_array

	while(i <= mid_index)
	{
		temp_array [k] = array[i];

		k++;
		i++;
	}


	//copy the right part of the array to temp_array

	while(j <= high)
	{
		temp_array [k] = array[j];

		k++;
		j++;
	}

	//copy the tem_array to original array

	for(i =0 ; i <= high; i++)
	{
		array[i] = temp_array[i];
	}

}


void merge_sort (int array[], int low, int high)
{
	int mid_index = 0;
	if (low < high)
	{
		mid_index = (low + high) / 2;
		merge_sort(array, low, mid_index);
		merge_sort(array, mid_index + 1, high);
		merge_sorted_array(array, low, mid_index, high);
	}
}

int main()
{
	int length = 0;
	int array[100];
	int index = 0;

	printf("Enter the length of the array\n");
	scanf("%d", &length);

	printf("Enter the array elements of length %d\n", length);

	for (index = 0; index < length; ++index)
	{
		scanf("%d", &array[index]);
	}

	merge_sort(array, 0, length - 1 );

	print_array(array, length);


}

输出：

Enter the length of the array
5
Enter the array elements of length 5
5
4
3
2
1
The sorted array is
1
2
3
4
5

最坏情况下的运行时间，用于“合并”排序：

Total time taken for merge sort = Time taken to sort left half + Time taken to sort left half +Time taken to merge left and right half.

T(n) = T (n/2) + T (n/2) + n
     = 2 T(n/2) + n ------> Equation 1

Now we need to calculate the time taken for T(n/2). Replace n with n/2 in equation 1.

T(n/2) = 2 * T(n/2/2) + n/2
       = 2T(n/2^2) + n/2 -------> Equation 2.

Now replace the value of n/2 from equation 2 to equation 1.

T(n) = 2 { 2T(n/2) + n/2) + n
     =2^2 T(n/2^2) + n + n 
     =2^2 * T (n/4) + 2n ----> Equation 3.

Now we need to find the value for T(n/4). Hence replace n with n/4 in equation 1, we get
T(n/4) = 2 T(n/8) + n/4.

Now replace the value of T(n/4) with the result above.

T(n) = 2^2 { 2T (n/8) + n/4)} + 2n
     = 2^3 * T(n/2^3) + n + 2n. [here 4 and n/4 cancels each other giving us “n”].
     = 2^3 * T(n/8) + 3n ----> Equation 4

Now again we need to calculate the value of T(n/8), by replacing in equation 1, and replacing in equation 4 we get:
     =2^4 * T (n/2^4) + 4n

Similarly, for T(n/2^4) we get
     = 2^5 * T(n/2^5) + 5n

Hence for ith value, we can write as:
T(n) = 2^i * T (n/2^i) + i*n ---> Equation 5

Once we recursively start to get the value of T(n/2^i), it will be reduced to 1.
Hence 
    n/2^i = 1
    n = 2^i  --->Equation 6
    i = log n ---> Equation 7
Now substitute equation 6 and 7 in 5 we get:

T(n) = n*T(1) + log n * n
	= n + n log n
	=O(n log n)

因此，在最坏的情况下，将进行合并排序 O（n log n） 时间。

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：