归并排序迭代实现
时间: 2023-06-29 11:13:59 浏览: 63
归并排序是一种经典的排序算法,主要思想是将待排序序列分成若干子序列,分别进行排序,最后合并成有序的序列。以下是归并排序的迭代实现:
```python
def merge_sort(arr):
n = len(arr)
step = 1 # 步长
while step < n:
i = 0
while i < n - step:
left = i # 左序列起始下标
right = i + step # 右序列起始下标
end = min(i + 2 * step, n) # 右序列结束下标
merged = []
l, r = left, right
while l < right and r < end:
if arr[l] <= arr[r]:
merged.append(arr[l])
l += 1
else:
merged.append(arr[r])
r += 1
while l < right:
merged.append(arr[l])
l += 1
while r < end:
merged.append(arr[r])
r += 1
arr[left:end] = merged
i += 2 * step
step *= 2
return arr
```
该算法的时间复杂度为 $O(n\log n)$ ,空间复杂度为 $O(n)$ 。