归并排序

归并排序是一种采用分治法策略的排序算法，其基本思想是将待排序序列分为两个子序列，对每个子序列分别进行排序，然后将两个有序子序列合并为一个有序序列。具体实现时，首先将原序列递归地分成两半，直到每个子序列只有一个元素，此时每个子序列都是有序的。接下来，采用自底向上的合并策略，每次将两个相邻的有序子序列合并成一个更大的有序子序列，直到所有子序列合并成一个有序序列。归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。