归并排序

归并排序是一种采用分治法策略的排序算法，其基本思想是将待排序序列分为两个或更多个子序列，每个子序列都是有序的，然后将这些有序的子序列合并成一个更大的有序序列。具体实现时，首先将待排序序列递归地分成两半，直到每个子序列只包含一个元素，此时每个子序列都是有序的。接下来，将这些有序的子序列两两合并，得到一个新的有序序列。重复这个过程，直到所有子序列合并成一个大的有序序列。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。