虽然分治排序的复杂度(n*lgn)要比插入排序(n*n)要好,但分治排序需要在数据量较大时才能体现这种优势,这样就可以对分治排序做个优化,当数据量较少时,则采用插入排序,详细见代码,通过测试分割点选定了50,也就是数组尺寸小于50时采用插入排序,得到的运行时间如下:
时间(in AlexdeiMac):
n=5000000,time=44s
n=10000000,time=100s
n=50000000,time=603s
对比之前的分治排序,时间如下:
时间(in AlexdeiMac):
n=5000000,time=53s
n=10000000,time=117s
n=50000000,time=646s
基本可以看到使用2种算法混合比单纯使用分治法有一定的效率提升