归并排序
归并排序是一种基于分治技术的排序技术。最坏情况时间复杂度为Ο(n log n)，是最受推崇的算法之一。
合并排序首先将数组分成相等的两半，然后将它们以排序的方式合并。
归并排序是如何工作的？
为了理解归并排序，我们采用如下的未排序数组-
我们知道归并排序首先将整个数组迭代地分成相等的两半，除非达到原子值。我们在这里看到一个包含 8 个项目的数组被分成两个大小为 4 的数组。
这不会改变原始项目的出现顺序。现在我们将这两个数组分成两半。
我们进一步划分这些数组，我们得到了不能再划分的原子值。
现在，我们以与分解它们完全相同的方式组合它们。请注意这些列表的颜色代码。
我们首先比较每个列表的元素，然后将它们以排序的方式组合到另一个列表中。我们看到 14 和 33 处于排序位置。我们比较 27 和 10，在 2 个值的目标列表中，我们首先放置 10，然后是 27、我们更改了 19 和 35 的顺序，而 42 和 44 是按顺序放置的。
在合并阶段的下一次迭代中，我们比较两个数据值的列表，并将它们合并成一个找到的数据值列表，将所有数据按排序顺序排列。
最终合并后，列表应如下所示-
现在我们应该学习归并排序的一些编程方面。
算法
合并排序继续将列表分成相等的两半，直到它不能再被分割。根据定义，如果它只是列表中的一个元素，则对其进行排序。然后，归并排序合并较小的排序列表，同时保持新列表的排序。
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
伪代码
现在我们将看到归并排序函数的伪代码。正如我们的算法指出的两个主要功能-分割和合并。
合并排序与递归一起工作，我们将以相同的方式查看我们的实现。
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure
