归并排序：算法原理与实现

归并排序：算法原理与实现

归并排序（Merge Sort）是一种经典的排序算法，它采用分治策略（Divide and Conquer）来对数组进行排序。该算法的基本思想是将数组分成若干个较小的部分，分别对它们进行排序，然后合并成较大的部分，直到整个数组排序完成。归并排序因其高效和稳定性在计算机科学中有着广泛的应用。

算法原理

1. 分解（Divide）：将待排序的数组从中间分成两个子数组。
2. 解决（Conquer）：递归地对两个子数组进行归并排序。
3. 合并（Merge）：将两个已排序的子数组合并成一个有序的数组。

算法实现

Python 示例

def merge_sort(arr):     if len(arr) <= 1:         return arr      mid = len(arr) // 2     left_half = arr[:mid]     right_half = arr[mid:]      merge_sort(left_half)     merge_sort(right_half)      i, j, k = 0, 0, 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: