三路归并排序时间复杂度

三路归并排序是一种归并排序的变体，它将待排序的数组划分为三个子区间，分别进行归并排序，然后再将三个有序的子区间合并成一个有序的数组。三路归并排序的时间复杂度可以通过以下步骤进行分析：

1. 划分子区间：将待排序的数组划分为三个子区间，每个子区间的长度大致相等。

2. 归并排序：对每个子区间进行归并排序，这一步的时间复杂度可以表示为T(n/3)，其中n是待排序数组的长度。

3. 合并子区间：将三个有序的子区间合并成一个有序的数组。这一步的时间复杂度可以表示为O(n)，其中n是待排序数组的长度。

综上所述，三路归并排序的时间复杂度可以表示为：
T(n) = 3 * T(n/3) + O(n)

根据主定理（Master Theorem），可以得到三路归并排序的时间复杂度为O(nlogn)。