912. Sort an Array.md

912. Sort an Array (Medium)

Algorithm 1. Quick Sort

#quick sort
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums) - 1
        self.sort_array_recursion(nums, left, right)
        return nums
        # pivot = self.partition(nums, left, right)
        # self.sort_array_recursion(nums, left, pivot - 1)
        # self.sort_array_recursion(nums, pivot + 1, right)
        
    def sort_array_recursion(self, nums, left, right):
        if left >= right:
            return
        mid = left + (right - left ) // 2
        pivot = nums[mid]
        i, j = left, right
        while(i <= j):
            while i <= j and nums[i] < pivot:
                i += 1
            while i <= j and nums[j] > pivot:
                j -= 1
            if i <= j:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
        self.sort_array_recursion(nums, left, j)
        self.sort_array_recursion(nums, i, right)

Algorithm 2. Merge Sort

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        ans = [0 for _ in range(len(nums))]
        self.merge_sort(nums, 0, len(nums) - 1, ans)
        return nums
    def merge_sort(self, nums, start, end, ans):
        if start >= end:
            return 
        mid = start + (end - start) // 2
        self.merge_sort(nums, start, mid, ans)
        self.merge_sort(nums, mid + 1, end, ans)
        self.merge(nums, start, mid, end, ans)
    def merge(self, nums, start, mid, end, ans):
        left, right = start, mid + 1
        index = start
        while left <= mid and right <= end:
            # cannot be equal, if equal add left to array
            if nums[left] < nums[right]:
                ans[index] = nums[left]
                left, index = left + 1, index + 1
            else:
                ans[index] = nums[right]
                right, index = right + 1, index + 1
        
        while left <= mid:
            ans[index] = nums[left]
            left, index = left + 1, index + 1
        while right <= end:
            ans[index] = nums[right]
            right, index = right + 1, index + 1
        
        for i in range(start, end + 1):
            nums[i] = ans[i]