递归与分治——√n段合并排序算法

思路：
分治法的原理是（1）找出基线条件 （2）缩小问题的规模，使其符合极限条件。
在本题中，首先需要解决的是划分数组的问题，规定将a[0,n-1]的数组划分为根号n个子数组（向下取整）。在这里的基线条件就是根号n。但是，根据数组数量，会存在除不尽的情况，可以通过递归调用的方法，再将数列进行分割排序。之后将每个数组单独排序成有序数列，最后将有序数组通过归并排序来合并。

用python代码实现

import math
import random

arr=[]
list=[]
output=[]


#生成数组一个范围在（0，100）间的数组arr
for i in range(48):
    arr.append(random.randint(0,100))

#打印原数组
print("原数组为"+str(arr))
print("数组长度为"+str(len(arr)))


#递归划分并合并排序
def cut(arr):
    

    #若已经划分到最小，则直接返回
    if(len(arr)<2):
        return arr
    
    #向下取整
    n=math.sqrt(len(arr))
    print("根号n为"+str(n))
    
    middle=math.floor(n)
    print("子数列长度为"+str(middle))
    j=0
    i=0
    for j in range (middle):
        
        child = arr[i:i+middle]
        i=i+middle
        child.sort()
        list.append(child)
        print("划分数组为"+str(child))
        
    child=arr[i:len(arr)]
    list.append(child)
    print("剩下的数列为"+str(child))
    
    #长度大于2时继续划分
    if len(child)>2:
        cut(child)



def merge_sort(list):
    num=len(list)
    i=0
    for i in range (0,num-1,2) :
        
        list[i]=merge(list[i],list[i+1])
        
    #清除空元素  
    for a in list:
        
        if (a==[]) :
            list.remove(a)
    #长度大于1时，继续合并        
    if(len(list)>1):
        merge_sort(list)
              
    
#归并排序
def merge(left,right):
    #存放结果
    result=[]
    while left and right:        
        #弹出相对小的数，放到新数组
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    #当数组不为空时，把剩余的数放进数组
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

def main():
    print(cut(arr))

    merge_sort(list)

    print("排序后的数组为"+str(list[0]))

main()