考虑到由于python执行效率不高，使用纯py实现MergeSort归并排序并没有太大价值，因此选择
Cython(语法类似Python) 。它可以把代码编译成调用了 Python 源码的 C/C++ 代码，从而提高执行效率
由于代码最终被编译为py库，所以需要先根据官方说明文档编写以下配置代码
# cython: language_level=3
# merge_sort_setup.py
from distutils.core import setup
from Cython.Build import cythonizesetup(ext_modules = cythonize("merge_sort.pyx")
)
再在同目录以cython语法编写排序算法
# cython: language_level=3
# merge_sort.pyx
cimport cython
from cpython.mem cimport PyMem_Malloc, PyMem_Free
from libc.string cimport memcpy@cython.boundscheck(False)
@cython.wraparound(False)def sort(list l): #从小到大排列listcdef int length = len(l), cnt = 0cdef int* clist = <int*>PyMem_Malloc(length * sizeof(int))for i in l:if isinstance(i, int):clist[cnt] = icnt += 1else: return [] #如果不是纯数字则返回空listreturn getList(_csort(clist, length), length)cdef int* _csort(int* l, int length):cdef int half, a, b, c, *list1, *list2, *listRetif length > 2:half = int(length/2)list1 = _csort(cutList(l,0,half), half)list2 = _csort(cutList(l,half,length - half), length - half)a, b, c = 0, 0 ,0PyMem_Free(l)listRet = <int*>PyMem_Malloc(length * sizeof(int))while a < half and b < length - half and c < length:if list1[a] <= list2[b]:listRet[c] = list1[a]a += 1else:listRet[c] = list2[b]b += 1c += 1while a < half:listRet[c] = list1[a]a += 1c += 1while b < length - half:listRet[c] = list2[b]b += 1c += 1PyMem_Free(list1)PyMem_Free(list2)return listRetelif length == 2:if l[0] > l[1]: l[0], l[1] = l[1], l[0]return lelse: return lcdef inline int* cutList(int* res, int start, int length):cdef int* des = <int*>PyMem_Malloc(length * sizeof(int))memcpy(des, res + start, length * sizeof(int))return descdef inline getList(int* res, int length):cdef int cnt = 0re = []while cnt < length:re.append(res[cnt])cnt += 1PyMem_Free(res)return re
接下来使用如下命令即可生成库文件
python3 merge_sort_setup.py build_ext --inplace
import进行测试
$ python3
Python 3.8.5 (default, Jul 21 2020, 10:42:08)
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import merge_sort
>>> merge_sort.sort([11,10,9,8,7,6,5,4,3,2,1])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> merge_sort.sort([9,8,7,6,5,4,3,2,1])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> merge_sort.sort([9,8,7,6,5,4,3,2,1,3,234,23524,23433,5789,432,676,234123,2,56856,213124])
[1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 9, 234, 432, 676, 5789, 23433, 23524, 56856, 213124, 234123]