Я считаю, что можно достичь O (N * log (K)), но не в худшем случае.
Рассмотрите возможность сортировки этих списков:
{0,1,2,3,4,5,6,7,8,9,10},
{10,11,12,13,14,15,16,17,18,19,20},
{20,21,22,23,24,25,26,27,28,29,30}
Мой человеческий мозг может легко сортировать эти списки, не считывая каждое значение, поэтому должен быть алгоритм, который может сделать то же самое. Нам нужно объединить при использовании модифицированного бинарного поиска для поиска диапазонов значений.
В худшем случае вы получите O (N * K), потому что каждое значение должно сравниваться. Пример:
{0,2,4,6,8},
{1,3,5,7,9}
Вот мое решение в Go, которое я использовал бы, только если бы знал, что отсортированные списки обычно имеют области перекрытия, которые малы по отношению к K:
// variation of binary search that finds largest
// value up to and including max
func findNext(a []int, imin int, vmax int) int {
imax := len(a) - 1
best := -1
for imin <= imax {
imid := imin + ((imax - imin) / 2)
if a[imid] == vmax {
return imid
} else if a[imid] < vmax {
best = imid
imin = imid + 1
} else {
imax = imid - 1
}
}
return best
}
func sortNSortedLists(in [][]int) []int {
var out []int
cursors := make([]int, len(in))
for {
// Find the array indices that have the smallest
// and next to smallest value (may be same) at
// their current cursor.
minIdx1 := -1
minIdx2 := -1
minVal1 := math.MaxInt32
minVal2 := math.MaxInt32
for i, cursor := range cursors {
if cursor >= len(in[i]) {
continue
}
if in[i][cursor] < minVal1 {
minIdx2 = minIdx1
minVal2 = minVal1
minIdx1 = i
minVal1 = in[i][cursor]
} else if in[i][cursor] < minVal2 {
minIdx2 = i
minVal2 = in[i][cursor]
}
}
if minIdx1 == -1 {
// no values
break
}
if minIdx2 == -1 {
// only one array has values, so append the
// remainder of it to output
out = append(out, in[minIdx1][cursors[minIdx1]:]...)
break
}
// If inVal1 is smaller than inVal2,
// append to output all values from minVal1 to minVal2 found in
// the minIdx1 array, and update the cursor for the minIdx1 array.
if minVal1 < minVal2 {
firstCursor := cursors[minIdx1]
lastCursor := findNext(in[minIdx1], firstCursor, minVal2)
if lastCursor != -1 {
out = append(out, in[minIdx1][firstCursor:lastCursor+1]...)
cursors[minIdx1] = lastCursor+1
continue
}
}
// Append the single value to output
out = append(out, minVal1)
cursors[minIdx1]++
}
return out
}