在 O(n log log n) 中排序 log (n) 个已排序的子序列
Sorting log (n) sorted subsequences in O(n log log n)
我有 log(n) 个成对排序的子序列（长度可能不同），我需要在 O(n log log n) 中排序，
但我不知道怎么做。我考虑过使用合并排序，但时间复杂度为 O(n log n)。
使用 bottom up natural merge sort。如果稳定性不是要求，则使用乱序序列来指示 运行 的结尾（代码还需要使用数组的结尾作为 运行 的结尾）。如果需要稳定性，您需要创建第二个计数数组（或指针）来跟踪 运行 边界，以防止两个或多个 运行 被视为单个 运行由于在合并过程中有两个或更多 运行 是有序的。由于初始状态是 log(n) 运行s，因此自下而上的自然合并排序将采用 log(log(n)) 遍，时间复杂度为 O(n log(log(n))。
我有 log(n) 个成对排序的子序列（长度可能不同），我需要在 O(n log log n) 中排序， 但我不知道怎么做。我考虑过使用合并排序，但时间复杂度为 O(n log n)。
使用 bottom up natural merge sort。如果稳定性不是要求，则使用乱序序列来指示 运行 的结尾（代码还需要使用数组的结尾作为 运行 的结尾）。如果需要稳定性，您需要创建第二个计数数组（或指针）来跟踪 运行 边界，以防止两个或多个 运行 被视为单个 运行由于在合并过程中有两个或更多 运行 是有序的。由于初始状态是 log(n) 运行s，因此自下而上的自然合并排序将采用 log(log(n)) 遍，时间复杂度为 O(n log(log(n))。