用python代码并使用分治法实现一组无序序列的两路合并排序和快速排序，并给出不同输入数据规模下最好、最坏、平均情况下的多次实验平均时间

在Python中，我们可以分别用分治法实现归并排序（Merge Sort）和快速排序（Quick Sort）。这里是这两种算法的基本实现：

**归并排序（Merge Sort）：**

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 示例：
arr = [4, 2, 9, 6, 1]
sorted_arr = merge_sort(arr)

**快速排序（Quick Sort）：**

def quick_sort(arr, low=None, high=None):
    if low is None:
        low = 0
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

# 示例：
unsorted_arr = [4, 2, 9, 6, 1]
quick_sort(unsorted_arr)

关于性能分析：
- **最好情况（Best Case）**：对于归并排序，无论输入如何都是O(n log n)，因为总是将数组分成对等部分进行递归。对于快速排序，在每次分区操作都能均匀分割的情况下，也是O(n log n)。
- **最坏情况（Worst Case）**：快速排序在输入完全有序或者几乎有序的情况下最慢，变为O(n^2)，因为分区过程可能会导致递归树退化成链状。而归并排序始终是稳定的O(n log n)。
- **平均情况（Average Case）**：快速排序通常有较好的平均性能，约为O(n log n)，接近于最优。

为了获取不同输入数据规模下的时间性能，你需要编写一个循环，创建不同长度的随机数组，然后记录每次排序的时间并计算平均值。这需要额外引入一些库如`timeit`来进行准确的计时。由于这里无法直接演示实际运行，你可以自己尝试编写这样的测试脚本，例如：

import random
import timeit

for n in [10**i for i in range(1, 5)]:  # 测试从10到10000的数据规模
    arr = [random.randint(0, 10000) for _ in range(n)]
    
    # 记录归并排序时间
    merge_sort_time = timeit.timeit(lambda: merge_sort(arr.copy()), number=1)
    print(f"Merge Sort on {n} elements: {merge_sort_time:.6f} seconds")

    # 记录快速排序时间
    quick_sort_time = timeit.timeit(lambda: quick_sort(arr.copy()), number=1)
    print(f"Quick Sort on {n} elements: {quick_sort_time:.6f} seconds")
    
    # 提示相关问题