mergesort算法
时间: 2023-12-07 07:39:09 浏览: 32
以下是mergesort算法的Python实现:
```python
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
```
该算法的基本思想是将待排序的序列分成两个子序列,对每个子序列进行递归排序,然后将两个已排序的子序列合并成一个有序的序列。具体实现中,使用了分治法的思想,将序列分成两个子序列,然后递归地对每个子序列进行排序,最后将两个已排序的子序列合并成一个有序的序列。