Leetcode 912. Sort an Array

Problem

Leetcode 912 - Sort an Array

Example:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Approach

This is just a simple sorting question, but since question states that we solve this problem using $O(n log n)$ time complexity and with the smallest complexity possible, we can use either Quick sort or Merge sort. Since Quick sort could be $O(n^2)$, we will be using Merge Sort to solve this problem. More information on Merge Sort can be found here.

Here is the Python code for the solution:

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        # merge sort
        def mergeSort(arr, l, r):
            # if left pointer is equal to right pointer, we return array
            if l == r:
                return arr

            # get mid pointer
            mid = (l+r) // 2

            # perform mergeSort on left to mid
            mergeSort(arr, l, mid)
            # perform mergeSort on mid to right
            mergeSort(arr, mid+1, r)
            # merge the array
            merge(arr, l, mid, r)
            
            return arr

        # merge
        def merge(arr, L, M, R):
            # split the array into half left, and right
            left, right = arr[L:M+1], arr[M+1: R+1]

            # i represents the index of array
            # j represents pointer of left array
            # k represents pointer of right array
            i, j, k = L, 0, 0

            # while j is less than legnth of left and k is less than length of right
            while j < len(left) and k < len(right):
                # check what's lower if left is lower, then arr[i] = left[j]
                if left[j] <= right[k]:
                    arr[i] = left[j]
                    j += 1
                # if right is lower, then arr[i] = right[k]
                else:
                    arr[i] = right[k]
                    k += 1
                i += 1

            # After we're done iterating first time, there is a chance where we didn't finish merging left
            while j < len(left):
                arr[i] = left[j]
                j += 1
                i += 1

            # AFter we're done iterating first time, there is a chance where we didn't finish merging right
            while k < len(right):
                arr[i] = right[k]
                k += 1
                i += 1

        mergeSort(nums, 0, len(nums))
        return nums

Time Complexity and Space Complexity

Time Complexity: $O(n log n)$

Space Complexity: $O(n)$