k路合并是将k个大小为n的排序数组作为输入的算法。它输出所有元素的单个排序数组。
通过使用合并排序算法中心的“合并”例程将数组1合并到数组2，然后将数组3合并到此合并的数组，依此类推，直到所有k个数组都合并为止。
我以为该算法为O（kn），因为该算法遍历k个数组（每个数组的长度为n）一次。为什么是O（nk ^ 2）？
因为它不会遍历k个数组中的每一个。第一个数组被遍历k-1次，第一个作为merge（array-1，array-2），第二个作为merge（merge（array-1，array-2），array-3）…依此类推。
结果是k-1合并，平均大小为n （k + 1）/ 2，给出的复杂度为O（n （k ^ 2-1）/ 2），即O（nk ^ 2）。
您犯的错误是忘记了合并是串行而不是并行进行的，因此数组的大小并非都为n。
