四路归并排序：分解时分成四个，合并等其他步骤与二路归并相似，请写出核心算法，并分析时间复杂度

四路归并排序是一种针对特定数据结构（例如，当数据已经部分有序，分为四个独立区间的情况）的优化版归并排序算法。它将数组划分为四个部分，分别对每个部分进行排序，然后再逐步合并。核心算法可以分为以下几个步骤：

1. **分割**（类似二分法）：首先将待排序数组递归地划分成四个长度相等的部分，如果数组长度不是4的倍数，则可能会有一个较小的部分。

2. **排序**：对每个部分进行单独的排序，可以采用递归的方式继续应用归并排序直到子序列只包含一个元素（此时视为已排序）。

3. **合并**：从四个部分的起始位置开始，每次取两个部分的最小值进行合并，形成新的有序序列，然后依次向后移动指针，直到所有的子序列都合并完成。

以下是简化的Python示例核心算法：

def merge_sort_quartiles(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 4
    left1, left2, right1, right2 = arr[:mid], arr[mid:2*mid], arr[2*mid:3*mid], arr[3*mid:]

    left1 = merge_sort_quartiles(left1)
    left2 = merge_sort_quartiles(left2)
    right1 = merge_sort_quartiles(right1)
    right2 = merge_sort_quartiles(right2)

    return merge(left1, left2, right1, right2)

def merge(left, mid, right, end):
    result = []
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(mid) and k < len(right) and k < end:
        if (left[i] <= mid[j]) and (left[i] <= right[k]):
            result.append(left[i])
            i += 1
        elif (mid[j] <= right[k]):
            result.append(mid[j])
            j += 1
        else:
            result.append(right[k])
            k += 1

    # 合并剩余元素
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(mid):
        result.append(mid[j])
        j += 1
    while k < len(right) and k < end:
        result.append(right[k])
        k += 1

    return result[:end]

**时间复杂度分析**：
尽管四路归并排序在划分阶段增加了工作量，但由于合并过程仍然是O(n)，所以总的归并操作次数依然是log n级别。因此，四路归并排序的时间复杂度仍然保持在O(n log n)，与标准归并排序一致。然而，在某些特定的数据分布下，如部分有序的数据，实际运行效率可能会有所提高。