归并排序：
归并排序是一种分治算法，它的原理是将待排序的数组不断分割成更小的子数组，直到每个子数组只有一个元素为止，然后将这些子数组按照大小顺序合并起来，最终得到一个有序的数组。
具体步骤如下：
- 将待排序的数组分成两个子数组，然后分别对这两个子数组进行归并排序。
- 将两个已经排序好的子数组合并成一个有序的数组。这里需要一个额外的数组来存放合并后的结果。
- 重复以上步骤，直到所有的子数组都合并成一个完整的有序数组。
代码实现：
n=int(input()) #要排序的数组的长度 ls=list(map(int,input().split())) # 输入要排序的数组 def MergeSort(ls): if len(ls)<=1: return ls mid = int(len(ls)/2) # 对原列表进行分治 llist,rlist=MergeSort(ls[:mid]),MergeSort(ls[mid:]) #再次分治调用自身 缩短要排序的长度 result=[] i,j=0,0 while i<len(llist) and j<len(rlist): if rlist[j]<llist[i]: result.append(rlist[j]) j+=1 else: result.append(llist[i]) i+=1 result += llist[i:]+rlist[j:] return result for j in MergeSort(ls): #输出结果 print(j,end=' ')
复杂度：
归并排序是一种稳定的排序算法，时间复杂度为O(nlogn)，空间复杂度为O(n)。它的主要优点是可以对链表等非随机访问的数据结构进行排序，并且在最坏情况下的时间复杂度也是O(nlogn)。
