Medium

Sort an Array

LAB

Return nums sorted in ascending order.

EXAMPLES

Example 1

Input
{
  "nums": [
    5,
    2,
    3,
    1
  ]
}

Output
[
  1,
  2,
  3,
  5
]

FUNCTION SHAPE

nums: intArray→intArray

SOLUTION NOTE

Using this merge(A,B) function, we can write the pseudocode for merge Sort. (don't forget for recursion the base case, if length 1 we are already sorted.)

Merge Sort Pseudocode:

textEXAMPLE

mergeSort(A):
    N = len(A)
    If N == 1: return A
    Left = mergeSort(A[:N//2])
    Right = mergeSort(A[N//2:])
    Return merge(Left, Right)

We can model the time taken as: T(n) = 2*T(n//2) + O(n), which is T(n) = O(nlogn) using master theorem. This is because we split into 2 subproblems of n//2, and at each step we do O(n) work in the merge(A,B) function.

Reveal reference solution +

pythonREFERENCE

def sortArray(self, nums: List[int]) -> List[int]:
    def merge(A, B):
        i = j = 0
        m, n = len(A), len(B)
        res = []
        while i < m and j < n:
            if A[i] < B[j]:
                res.append(A[i])
                i += 1
            else:
                res.append(B[j])
                j += 1

        while i < m:
            res.append(A[i])
            i += 1
        while j < n:
            res.append(B[j])
            j += 1
        return res

    def mergeSort(nums):
        n = len(nums)
        if n <= 1: return nums

        left = mergeSort(nums[:n//2])
        right = mergeSort(nums[n//2:])

        return merge(left, right)

    return mergeSort(nums)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗