归并排序

归并排序是一种遵循分治范式的排序算法。它由约翰·冯·诺依曼于1945年发明。该算法的工作原理是将一个未排序的列表分成n个分区，每个分区包含一个元素（一个元素的列表被认为是已排序的），然后反复合并分区以生成新的已排序列表，直到只剩下一个已排序列表为止。这个最终生成的列表就是完全排序的列表。将列表分割的过程是递归完成的，直到达到只有一个元素的列表的基准情况。归并排序在所有情况下（最佳、平均和最坏）的时间复杂度都是O(n log n)，这使得它在处理大型数据集时非常高效。