Quick Sort & Merge Sort in Python, Easy to Understand, Standard Template!
Two Methods:\n1. Quick Sort\n2. Merge Sort\n\n1. Standard Quick Sort Tempate,\n\nIn the while loop, the reason we use "nums[left] < pivot" instead of "nums[left
**Two Methods:**\n**1. Quick Sort**\n**2. Merge Sort**\n\n**1. Standard Quick Sort Tempate**,\n\nIn the while loop, the reason we use "**nums[left] < pivot**" instead of "nums[left] <= pivot" is to **avoid falling into forever loop**.\n**For example:**\nnums = [1, 1, 1], pivot will be 1.\nIf we use "nums[left] <= pivot",\nending right index will be 2, ending left index will be 3,\nin the next round, we still have to go through [1, 1, 1], meaning that we fall in to forever loop.\n\n**Time:** on average O(nlgn), worst case O(n^2)\n**Space:** O(lgn), on average the recursion stack\n\n```\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        if not nums:\n            return nums\n        self.quickSort(0, len(nums) - 1, nums)\n        return nums\n    \n    def quickSort(self, start, end, nums):\n        if start >= end:\n            return\n        \n        left, right = start, end\n        pivot = nums[(left + right) // 2]\n        \n        while left <= right:\n            while left <= right and nums[left] < pivot:\n                left += 1\n            while left <= right and nums[right] > pivot:\n                right -= 1\n            if left <= right:\n                nums[left], nums[right] = nums[right], nums[left]\n                left += 1\n                right -= 1\n\n        self.quickSort(start, right, nums)\n        self.quickSort(left, end, nums)\n```\n\n**2. Standard Merge Sort Template**\n\nFor merge sort, I will provide **two methods:**\nthe first one with space complexity O(nlgn),\nthe second one with space complexity optimized to O(n).\n\n**Method 2.1: space complexity O(nlgn)**\n\n**Time:** O(nlgn)\n**Space:** O(nlgn)\n\n```\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        if not nums:\n            return nums\n        self.mergeSort(0, len(nums) - 1, nums)\n        return nums\n    \n    def mergeSort(self, start, end, nums):\n        if start >= end:\n            return \n        \n        middle = (start + end) // 2\n        \n        self.mergeSort(start, middle, nums)\n        self.mergeSort(middle + 1, end, nums)\n        self.merge(start, end, nums)\n    \n    def merge(self, start, end, nums):\n        tmp = [0] * (end - start + 1)\n        \n        middle = (start + end) // 2\n        left = start\n        right = middle + 1\n        index = 0\n        \n        while left <= middle and right <= end:\n            if nums[left] <= nums[right]:\n                tmp[index] = nums[left]\n                left += 1\n                index += 1\n            else:\n                tmp[index] = nums[right]\n                right += 1\n                index += 1\n        \n        while left <= middle:\n            tmp[index] = nums[left]\n            left += 1\n            index += 1\n        \n        while right <= end:\n            tmp[index] = nums[right]\n            right += 1\n            index += 1\n        \n        for i in range(end - start + 1):\n            nums[i + start] = tmp[i]\n```\n\n**Method 2.2: space complexity O(n)**\n\n**Time:** O(nlgn)\n**Space:** O(n)\n\n```\nclass Solution:\n    def sortArray(self, nums: List[int]) -> List[int]:\n        if not nums:\n            return nums\n        tmp = [0] * len(nums)\n        self.mergeSort(0, len(nums) - 1, nums, tmp)\n        return nums\n    \n    def mergeSort(self, start, end, nums, tmp):\n        if start >= end:\n            return \n        \n        middle = (start + end) // 2\n        \n        self.mergeSort(start, middle, nums, tmp)\n        self.mergeSort(middle + 1, end, nums, tmp)\n        self.merge(start, end, nums, tmp)\n    \n    def merge(self, start, end, nums, tmp):\n        \n        middle = (start + end) // 2\n        left = start\n        right = middle + 1\n        index = start\n        \n        while left <= middle and right <= end:\n            if nums[left] <= nums[right]:\n                tmp[index] = nums[left]\n                left += 1\n                index += 1\n            else:\n                tmp[index] = nums[right]\n                right += 1\n                index += 1\n        \n        while left <= middle:\n            tmp[index] = nums[left]\n            left += 1\n            index += 1\n        \n        while right <= end:\n            tmp[index] = nums[right]\n            right += 1\n            index += 1\n        \n        for i in range(start, end + 1):\n            nums[i] = tmp[i]\n```
['Sorting', 'Merge Sort', 'Python']