对已排序数组的串联进行排序

Question

对于由 2 个已排序子数组组成的数组进行排序，最优化的排序算法是什么？

我在解的时候出现了这个问题：https://leetcode.com/problems/squares-of-a-sorted-array/

我的解决方法如下：

    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        l, r = 0, n-1
        res = [0] * n
        
        for i in range(n-1, -1, -1):
            if abs(nums[l]) > abs(nums[r]):
                res[i] = nums[l] ** 2
                l += 1
            else:
                res[i] = nums[r] ** 2
                r -= 1
        return res

但是这个解决方案胜过我的：

    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted([i * i for i in nums])

如果 timsort 对小块进行插入排序，那么像这样的数组不会在一半的运行中导致 O(n^2) 吗？这比我所谓的 O(n) 解决方案好在哪里？

谢谢！

Answer 1

在这种情况下，理论时间复杂度为O(n)，因为您根本不需要排序（只需合并两个有序列表）。执行排序通常具有 O(NlogN) 复杂度。

然而，复杂性和性能是两个不同的东西。 Python 代码中的 O(n) 解决方案正在与高度优化的低级 C 代码中的 O(NlogN) 竞争。理论上应该有一个点，其中列表的大小足以让基于 Python 的 O(n) 解决方案赶上本机排序的 O(NlogN) 配置文件，但您可以预期这会是大量的元素（可能比您的计算机内存可以容纳的大）。如果 Python 的原生排序足够聪明，可以切换到整数的基数排序算法，或者如果它的排序算法受益于部分排序的数据，那么它将无法赶上。

对已排序数组的串联进行排序

sorting a concatenation of sorted arrays

python

arrays

sorting

timsort