归并排序代码（归并排序代码更短）

归并排序是一种常用的排序算法，它通过将待排序的数组划分为若干个子数组，然后将子数组进行排序，并最终合并成一个有序数组。它采用了分治思想，将问题拆分成子问题，然后分别解决子问题，最后将解得的子问题合并起来得到最终结果。

## 算法思想

归并排序的主要思想是将待排序数组不断地划分为两个子数组，直到不能再划分为止。然后对子数组进行排序，并将排序好的子数组合并起来得到最终结果。

具体步骤如下：

1. 将待排序数组平分为两个子数组，不断地进行递归操作，直到无法再分割。

2. 对每个子数组进行排序，可以使用递归或其他排序算法（如插入排序、冒泡排序等）。

3. 将排序好的子数组合并起来，得到最终结果。

## 代码实现

下面是使用Python实现归并排序算法的代码：

```python

def merge_sort(arr):

if len(arr) <= 1:

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_half, right_half):

result = []

i, j = 0, 0

# 比较两个子数组的元素，并按照顺序合并到结果数组中

while i < len(left_half) and j < len(right_half):

if left_half[i] < right_half[j]:

result.append(left_half[i])

i += 1

else:

result.append(right_half[j])

j += 1

# 将剩余的元素添加到结果数组中

result.extend(left_half[i:])

result.extend(right_half[j:])

return result

# 测试代码

arr = [4, 7, 2, 5, 1, 9, 8, 6, 3]

sorted_arr = merge_sort(arr)

print(sorted_arr)

```

## 总结

归并排序是一种高效的排序算法，它采用了分治思想，将问题拆分成子问题然后分别解决，在合并子问题的过程中得到最终结果。通过将数组不断地划分并排序，归并排序能够将待排序的数组快速有序化。它的时间复杂度为O(nlogn)，但由于需要额外的空间存储子数组，所以空间复杂度较高。然而，归并排序的稳定性和良好的适应性使得它在实际应用中得到广泛使用。