合并排序是基于分治算法原理的最流行的排序算法之一。使用合并算法，一个问题被分成多个子问题。每个子问题都是单独解决的。最后，将子问题组合起来形成最终解决方案。
分而治之的思想
使用分而治之的技术，我们将问题划分为子问题。当每个子问题的解决方案准备就绪时，我们“合并”子问题的结果来解决主要问题。
它将给定的列表分成相等的两半，子列表被一次又一次地分成两半，直到列表不能被进一步分割。然后我们将一对单元素列表组合成双元素列表，并在此过程中对它们进行排序。排序后的二元素数组被合并到四元素列表中，依此类推，直到我们得到排序列表。
合并排序算法
在下面的算法中，arr是给定的数组，beg是开始的下标，end是结束的元素下标
归并排序的重要部分是MERGE函数。此函数执行合并两个排序的子数组A[beg...mid]和A[mid+1...end]，以构建一个排序数组A[beg...end]。因此，MERGE函数的输入是A[]、beg、mid和end。
merge函数的实现如下:
/* Function to merge the subarrays of a[] */voidmerge(inta[], intbeg, intmid, intend) { inti, j, k; intn1=mid-beg+1; intn2=end-mid; intLeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */for (inti=0; i<n1; i++) LeftArray[i] =a[beg+i]; for (intj=0; j<n2; j++) RightArray[j] =a[mid+1+j]; i=0, /* initial index of first sub-array */j=0; /* initial index of second sub-array */k=beg; /* initial index of merged sub-array */while (i<n1&&j<n2) { if(LeftArray[i] <=RightArray[j]) { a[k] =LeftArray[i]; i++; } else { a[k] =RightArray[j]; j++; } k++; } while (i<n1) { a[k] =LeftArray[i]; i++; k++; } while (j<n2) { a[k] =RightArray[j]; j++; k++; } }
合并排序原理
为了理解归并排序算法的工作原理，我们来看一个未排序的数组。通过示例更容易理解归并排序。
数组的元素如下所示
根据归并排序，首先将给定数组分成相等的两半。合并排序不断将列表分成相等的部分，直到它无法进一步划分。
由于给定数组中有八个元素，因此将其分为两个大小为 4 的数组。
再次将这两个数组分成两半。由于它们的大小为 4，因此将它们分成大小为 2 的新数组。
再次划分这些数组以获得无法进一步划分的原子值。
接下来对数组进行组合，首先比较每个数组的元素，然后将它们按排序顺序组合成另一个数组。
因此，首先比较 12 和 31，两者都在排序位置。然后比较 25 和 8，在两个值的列表中，先放 8，后放 25。再比较 32 和 17，排序，先放 17，后放 32。然后比较 40 和 42，依次排列。
在组合的下一次迭代中，现在将数组与两个数据值进行比较，并将它们按排序顺序合并到一个找到的值数组中。
现在，有一个数组的最终合并。上述数组最终合并后，数组将如下所示 ：
合并排序复杂度
时间复杂度
空间复杂度为0(n)
Java实现算法
classMerge { /* Function to merge the subarrays of a[] */voidmerge(inta[], intbeg, intmid, intend) { inti, j, k; intn1=mid-beg+1; intn2=end-mid; /* temporary Arrays */intLeftArray[] =newint[n1]; intRightArray[] =newint[n2]; /* copy data to temp arrays */for (i=0; i<n1; i++) LeftArray[i] =a[beg+i]; for (j=0; j<n2; j++) RightArray[j] =a[mid+1+j]; i=0; /* initial index of first sub-array */j=0; /* initial index of second sub-array */k=beg; /* initial index of merged sub-array */while (i<n1&&j<n2) { if(LeftArray[i] <=RightArray[j]) { a[k] =LeftArray[i]; i++; } else { a[k] =RightArray[j]; j++; } k++; } while (i<n1) { a[k] =LeftArray[i]; i++; k++; } while (j<n2) { a[k] =RightArray[j]; j++; k++; } } voidmergeSort(inta[], intbeg, intend) { if (beg<end) { intmid= (beg+end) /2; mergeSort(a, beg, mid); mergeSort(a, mid+1, end); merge(a, beg, mid, end); } } /* Function to print the array */voidprintArray(inta[], intn) { inti; for (i=0; i<n; i++) System.out.print(a[i] +" "); } publicstaticvoidmain(Stringargs[]) { inta[] = { 11, 30, 24, 7, 31, 16, 39, 41 }; intn=a.length; Mergem1=newMerge(); System.out.println("\nBefore sorting array elements are - "); m1.printArray(a, n); m1.mergeSort(a, 0, n-1); System.out.println("\nAfter sorting array elements are - "); m1.printArray(a, n); System.out.println(""); } }
