实现k路归并排序

def merge(left, right):
    result = []
    i = j = 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

def k_way_merge_sort(arr, k):
    if len(arr) <= 1:
        return arr
    
    # 将数组分成k个子序列
    sub_arrays = [arr[i::k] for i in range(k)]
    
    # 对每个子序列进行排序
    sorted_sub_arrays = [sorted(sub_array) for sub_array in sub_arrays]
    
    # 合并子序列
    while len(sorted_sub_arrays) > 1:
        merged_sub_arrays = []
        for i in range(0, len(sorted_sub_arrays), 2):
            if i + 1 < len(sorted_sub_arrays):
                merged_sub_arrays.append(merge(sorted_sub_arrays[i], sorted_sub_arrays[i + 1]))
            else:
                merged_sub_arrays.append(sorted_sub_arrays[i])
        sorted_sub_arrays = merged_sub_arrays
    
    return sorted_sub_arrays[0]

# 示例数据
arr = [3, 6, 8, 10, 1, 2, 1]
k = 3
sorted_arr = k_way_merge_sort(arr, k)
print(sorted_arr)