What is the sorting algorithm most optimized for sorting an array that consists of 2 sorted sub-arrays?
This question came up when I was solving: https://leetcode.com/problems/squares-of-a-sorted-array/
My solution is as follows:
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
However this solution beats mine:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted([i * i for i in nums])
If timsort is doing insertion sort on small chunks, then wouldn't an array like this cause O(n^2) on half the runs? How is that better than my supposedly O(n) solution?
Thank you!
In this case, the theoretical time complexity is O(n) because you don't need to sort at all (merely merge two ordered lists). Performing a sort generally has a O(NlogN) complexity.
Complexity and performance are two different things however. Your O(n) solution in Python code is competing with O(NlogN) in highly optimized low level C code. In theory there should be a point where the size of the list is large enough for the Python based O(n) solution to catch up with the O(NlogN) profile of the native sort but you can expect that this would be a very large number of elements (probably larger than your computer's memory can hold). If Python's native sort is smart enough to switch to a radix sorting algorithm for integers or if its sorting algorithm benefits from partially sorted data, it will be impossible to catch up.