三路归并得到递增序列（python语言）

Question

#python初学者，在学数据结构，求大家指教以下问题
#有3个递增有序序列L0,1,2，其中元素均为整数，最大元素不超过1000。编写一个实验程序采用三路归并得到递增有序序列L，L包含全部元素。要求：分别采用顺序存储结构和链式存储结构两种存储结构实现
书上只能学到二路归并的做法，三路归并我加了列表上去做不动程序，希望有人可以指导一下

Answer 1

归并排序的过程是：

1.将一个序列从中间位置分成两个序列。

2.再将这两个子序列按照第一步继续二分下去。

3.直到所有的子序列的长度都为1，即不可再二分为止。

4.最后再将所有的子序列两两归并成一个有序序列即可。

归并排序主要使用了分治法的思想。

分治法：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解决这些子问题，然后将各个子问题的解合并得到原问题的解。

python代码：

```python
#列表归并
def Merge(a,b):
    #用来存放归并后的列表
    c=[]
    #用来记录列表a已归并的长度
    h=0
    #用来记录列表b已归并的长度
    j=0
    #当h和j的长度都小于待归并的列表a和b的长度时，执行归并循环
    while h<len(a) and j<len(b):
        #如果列表a的开头数字比b的小
        if a[h]<b[j]:
            #则将列表a的开头数字添加到归并列表c中
            c.append(a[h])
            #同时a已归并的长度+1
            h=h+1
        else:
            #反之，则将列表b的开头数字添加到归并列表c中
            c.append(b[j])
            #同时b已归并的长度+1
            j=j+1
    #如果h等于列表a的长度，则意味着列表a已经归并完成
    if h==len(a):
        #将列表b剩下的值依次插入列表c中
        for i in b[j:]:
            c.append(i)
    else:
        #反之，则意味着列表b已经归并完成
        #将列表a剩下的值依次插入列表c中
        for i in a[h:]:
            c.append(i)
    #返回已经归并完成的列表c
    return c
 
 
#归并排序
def Merge_Sort(unsorted_list):
    #如果需要归并的列表长度为1，则不需要归并，直接返回列表
    if len(unsorted_list)==1:
        return unsorted_list
    #将待排序列表从中间一分为二，递归进行进行归并排序
    middle=len(unsorted_list)//2
    #待归并列表的左半边
    left=Merge_Sort(unsorted_list[:middle])
    #待归并列表的右半边
    right=Merge_Sort(unsorted_list[middle:])
    #返回左右两边的列表归并
    return Merge(left,right)
 
 

```