归并排序

归并排序是一种分治算法，它将数组分成两半，分别对它们排序，然后将排序好的两半合并在一起。以下是使用Python实现归并排序的一个示例：

def merge_sort(arr):
    if len(arr) > 1:
        # 找到中间索引
        mid = len(arr) // 2
        # 分别对两半进行排序
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)  # 递归对左半部分排序
        merge_sort(R)  # 递归对右半部分排序

        # 合并两个排序好的部分
        i = j = k = 0

        # 按顺序合并元素
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 如果左侧剩余元素，复制到arr中
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        # 如果右侧剩余元素，复制到arr中
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

    return arr

# 测试归并排序函数
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = merge_sort(arr)
print("Sorted array is:", sorted_arr)

当你运行这段代码时，它将输出排序后的数组：

Sorted array is: [5, 6, 7, 11, 12, 13]

归并排序是稳定的排序算法，其平均和最坏情况的时间复杂度均为O(n log n)，相比于冒泡排序，它更适合于大规模数据的排序任务。归并排序也常用于需要稳定排序的场合，例如数据库和索引的构建。