Python归并排序算法实现详解

何川

发布时间：2026-10-13| 5人浏览过

原创

本文介绍基于分治思想的Python归并排序实现。通过递归划分序列并合并有序子序列，展示二路归并的具体代码逻辑。包含完整的Merge与MergeSort函数定义及随机数组测试示例，适用于Python数据结构学习参考。

本文分享一个使用Python编写的归并排序程序实例，供读者参考学习。

归并排序是一种高效的排序算法，其核心建立在归并操作之上。该算法是分治法（Divide and Conquer）的典型应用之一。

其基本思路是将已存在的有序子序列进行合并，从而生成一个完全有序的序列。具体而言，先确保每个子序列内部有序，再使子序列之间的顺序有序。如果将两个有序表合并为一个有序表，这一过程被称为二路归并。

以下是Python语言的具体实现代码：

#-*- coding: UTF-8 -*-
import numpy as np
def Merge(a, f, m, l):
  i = f
  j = m + 1
  tmp = []
  while i <= m and j <= l:
    if a[i] <= a[j]:
      tmp.append(a[i])
      i += 1
    else:
      tmp.append(a[j])
      j += 1
  while i <= m:
    tmp.append(a[i])
    i += 1
  while j<= l:
    tmp.append(a[j])
    j+= 1
  i = f
  for x in xrange(0, len(tmp)):
    a[i] = tmp[x]
    i += 1
def MergeSort(a, f, l):
  if f< l:
    m = (l + f) / 2
    MergeSort(a, f, m)
    MergeSort(a, m+1, l)
    Merge(a, f, m, l)
if __name__ == '__main__':
  a = np.random.randint(0, 10, size = 10)
  print "Before sorting..."
  print "---------------------------------------------------------------"
  print a
  print "---------------------------------------------------------------"
  MergeSort(a, 0, a.size-1)
  print "After sorting..."
  print "---------------------------------------------------------------"
  print a
  print "---------------------------------------------------------------"

程序运行后的输出结果如下：