常见排序算法-归并排序

归并排序

归并排序是利用递归将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好的半子表合并为有序序列。

算法步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

设定两个指针，最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置，重复上述步骤直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

 1 def merge(s1,s2,s):
 2     i=j=0
 3     while i+j<len(s):
 4         if j==len(s2) or (i<len(s1) and s1[i]<=s2[j] ):
 5         # if j==len(s2) or  (s1[i]<=s2[j] and i<len(s1)  ):
 6             s[i+j]=s1[i]
 7             i+=1
 8         else:
 9             s[i+j]=s2[j]
10             j+=1
11 def merge_sort(array):
12     n=len(array)
13     if n<2:
14         return
15     mid=n//2
16     s1=array[:mid]
17     s2=array[mid:]
18     merge_sort(s1)
19     merge_sort(s2)
20     merge(s1,s2,array)
21 
22 if __name__=='__main__':
23     array1 = [2, 1, 6, 3, 5]
24     merge_sort(array1)
25     print(array1)