python归并排序

归并排序（Merge Sort）是一种经典的排序算法，它采用分治法的一个非常典型的应用。该算法将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。其基本步骤如下：
1. **分解**：将待排序的序列分解成若干个子序列，每个子序列都是有序的，且子序列的长度递减。通常分解到每个子序列只包含一个元素为止。
2. **归并**：将两个有序的子序列合并成一个有序的序列。在归并过程中，比较两个子序列中的元素，将较小的元素先放入结果序列中，然后从较小元素的子序列中继续取出元素与较大元素的子序列中的元素比较，重复此过程，直到两个子序列中的元素都已被合并到结果序列中。
3. **排序**：对分解得到的子序列进行归并，得到最终的有序序列。
归并排序的详细步骤如下：
- **分解**：将序列分解成子序列
? - 计算序列的中间位置，将序列分成两个子序列，左边的子序列包含从第一个元素到中间位置的所有元素，右边的子序列包含从中间位置+1到序列末尾的所有元素。
? - 对每个子序列递归地应用分解步骤，直到每个子序列的长度为1。
- **归并**：将子序列合并成有序序列
? - 取两个子序列的第一个元素进行比较，将较小的元素放入结果序列中，然后从较小元素的子序列中取出下一个元素与较大元素的子序列中的下一个元素进行比较，重复此过程，直到两个子序列中的所有元素都被合并到结果序列中。
? - 递归地应用归并步骤，将所有子序列合并成一个有序序列。
- **排序**：将分解和归并的结果合并，得到最终的有序序列。
归并排序的时间复杂度为O(nlogn)，其中n为序列的长度。虽然归并排序不是稳定的排序算法，但它能够保证在最坏情况、平均情况和最佳情况下都有相同的时间复杂度。此外，归并排序是一种外部排序算法，需要使用额外的存储空间来存储子序列。

归并排序是一种分治算法，它将一个数组分成两个子数组，然后分别对这两个子数组进行排序，最后将这两个有序的子数组合并成一个有序的数组。

下面是一个用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

? ? return arr
```

使用这个函数可以对一个数组进行归并排序：

```python

arr = [3, 6, 8, 10, 1, 2, 5, 7, 9]
sorted_arr = merge_sort(arr)
print(sorted_arr)
```

这将输出：[1, 2, 3, 5, 6, 7, 8, 9, 10]，表示数组已经按照升序排列。