归并排序递归算法程序实现
时间: 2024-08-27 19:03:35 浏览: 41
归并排序是一种基于分治策略的排序算法,它将待排序数组分为两半,分别对每一半进行排序,然后合并两个已排序的部分。以下是使用递归实现归并排序的Python示例:
```python
def merge_sort(arr):
if len(arr) <= 1: # 基线条件:长度为1或0的数组已经有序
return arr
# 分割数组
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# 递归地对左右两半进行排序
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
# 合并已排序的左右部分
return merge(left_half, right_half)
def merge(left, right):
merged = []
i = j = 0
# 比较并添加元素到新数组
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# 如果有剩余元素,追加至结果
merged.extend(left[i:])
merged.extend(right[j:])
return merged
# 示例用法
arr = [9, 7, 5, 11, 12, 2, 14, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)