O(nlog(n)) time complexity and with the smallest space complexity possible.
Examples:
Input: [5, 2, 8, 1, 9]
Output: [1, 2, 5, 8, 9]
Input: [5]
Output: [5]
The base case is when we reach an array of one element that we cannot further split. A single-element array is sorted by definition.
The recursive relationship is that we can merge two sorted arrays.
Hence, we can keep splitting until we reach single-element arrays and then start merging all the way to the top.
from typing import List
def sort_array(nums: List[int]) -> List[int]:
def merge(sortedArr1, sortedArr2):
i, j = 0, 0
n1, n2 = len(sortedArr1), len(sortedArr2)
ans = []
while i < n1 and j < n2:
if sortedArr1[i] < sortedArr2[j]:
ans.append(sortedArr1[i])
i += 1
else:
ans.append(sortedArr2[j])
j += 1
if j < n2:
i = j
sortedArr1 = sortedArr2
for k in range(i, len(sortedArr1)):
ans.append(sortedArr1[k])
return ans
def mergsort(a):
n = len(a)
if n == 1:
return a
a1, a2 = a[: n // 2], a[n // 2 :]
return merge(mergsort(a1), mergsort(a2))
return mergsort(nums)
We can run an example as follows:
## [1, 2, 5, 8, 9]
The time complexity of this solution is \(O(N log N)\). We divide in \(O(log N)\) and then we merge those halves which will take \(O(N)\) so \(O(N log N)\). Space complexity is \(O(N)\), since the recursive stack will use \(O(log N)\) and we also use an additional array
ansof space \(O(N)\).