# 0912. Sort an Array {% tabs %} {% tab title="❓ Problem Statement" %} > Source: [LeetCode - Sort an Array](https://leetcode.com/problems/sort-an-array/)\ > GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0912-sort-an-array) Given an array of integers `nums`, sort the array in ascending order. {% endtab %} {% tab title=" ✍🏻 Constraints & Example" %} **Constraints:** * `1 <= nums.length <= 5 * 10^4` * `-5 * 10^4 <= nums[i] <= 5 * 10^4` ``` Input: nums = [5,2,3,1] Output: [1,2,3,5] Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5] ``` {% endtab %} {% endtabs %} {% tabs %} {% tab title="💡 Ideas" %} There are numerous ways to sort an array or a linked list. I prefer to take **merge sort** for sorting an array or linked list, while quick sort can be implemented concisely. > Reference: LeetCode Discussion - [**Python**](https://leetcode.com/problems/sort-an-array/discuss/276916/Python-bubble-insertion-selection-quick-merge-heap), [**Python3**](https://leetcode.com/problems/sort-an-array/discuss/461394/Python-3-\(Eight-Sorting-Algorithms\)-\(With-Explanation\)), [**Java**](https://leetcode.com/problems/sort-an-array/discuss/492042/7-Sorting-Algorithms-\(quick-sort-top-downbottom-up-merge-sort-heap-sort-etc.\)) > {% endtab %} {% tab title="❶ Merge Sort" %} {% hint style="info" %} **Recursively divide** the input array into two halves, **then merge** them. {% endhint %} 1. For **dividing** the array, it is straightforward in Python by `array[:length // 2]` 2. For **merging and sorting two arrays**, excepting iterating through each element in two arrays, need to take care of the **remaining elements** due to unequal length of arrays. **Note** that we don't need to do division *when the input array has only one element*. ```python # Example: # array = [3, 4, 5, 2, 1] # n = 5 [3, 4, 5, 2, 1] --'divide'--> [3, 4], [5, 2, 1] # Part 1 # ------------------------------------------------- [3, 4] --'divide'--> [3], [4] [3], [4] --'merge'---> [3, 4] # Part 2 # ------------------------------------------------- [5, 2, 1] --'divide'--> [5], [2, 1] # Part 2' # ------------------------------------------------- [2, 1] --'divide'--> [2], [1] [2], [1] --'merge'---> [1, 2] # Merge Part 2 and Part 2' # ------------------------------------------------- [5], [1, 2] --'merge'---> [1, 2] + [5] = [1, 2, 5] # Merge Part 1 and Part 2 # ------------------------------------------------- [3, 4], [1, 2, 5] --'merge'--> [1, 2, 3, 4] + [5] = [1, 2, 3, 4, 5] ``` {% endtab %} {% tab title="❷ Quick Sort" %} {% hint style="info" %} **Recursively do partition** operation in each **Sorting** iteration. {% endhint %} 1. For **sorting** function, it serves as a wrapper to do partition and take care of the termination of recursion by **`rIndex == lIndex`** or **`rIndex - lIndex == 1`** 2. For **partitioning** operation, we randomly **pick a pivot** by the index. Then, we move elements with **smaller values to its left** side and move elements with **larger values to its right side** by **two pointers**. Finally, return pivot's index. ```python # Example: # array = [3, 4, 5, 2, 1] # n = 5 # quickSort(array, lIndex=0, rIndex=n=5) # Part 1: partition(array, lIndex=0, rIndex-1=4) [3, 4, '5', 2, 1] --> pivot = array[(lIndex + rIndex) // 2] = 5 # Step 1: Move pivot to the end by pivot=rIndex=4 [3, 4, '5', 2, 1] --> [3, 4, 1, 2, '5'] # Step 2: Using two pointers to move smaller elements to left [3, 4, 1, 2, '5'] --> [3, 4, 1, 2, '5'] # place-pointer = 4 # Step 3: Move back the Pivot by swapping place-pointer and rIndex [3, 4, 1, 2, '5'] --> [3, 4, 1, 2, '5'] # Step 4: Return place-pointer's index = 4 # Part 2: Sort sort(array, lIndex=0, rIndex=pivot=4) sort(array, lIndex=pivot + 1, rIndex=5) # lIndex == rIndex, done # ------------------------------------------ # Part 1: partition(array, lIndex=0, rIndex-1=3) [3, '4', 1, 2, 5] --> pivot = array[(lIndex + rIndex) // 2] = 4 # Step 1: Move pivot to the end by pivot=rIndex=3 [3, '4', 1, 2, 5] --> [3, 2, 1, '4', 5] # Step 2: Using two pointers to move smaller elements to left [3, 2, 1, '4', 5] --> [3, 2, 1, '4', 5] # place-pointer = 3 # Step 3: Move back the Pivot by swapping place-pointer and rIndex [3, 2, 1, '4', 5] --> [3, 2, 1, '4', 5] # Step 4: Return place-pointer's index = 3 # Part 2: Sort sort(array, lIndex=0, rIndex=pivot=3) sort(array, lIndex=pivot + 1, rIndex=4) # lIndex == rIndex, done # ------------------------------------------ # Part 1: partition(array, lIndex=0, rIndex-1=2) [3, '2', 1, 4, 5] --> pivot = array[(lIndex + rIndex) // 2] = 2 # Step 1: Move pivot to the end by pivot=rIndex=2 [3, '2', 1, 2, 5] --> [3, 1, '2', 4, 5] # Step 2: Using two pointers to move smaller elements to left [3, 1, '2', 4, 5] --> [1, 3, '2', 4, 5] # place-pointer = 1 # Step 3: Move back the Pivot by swapping place-pointer and rIndex [1, 3, '2', 4, 5] --> [1, '2', 3, 4, 5] # Step 4: Return place-pointer's index = 1 # Part 2: Sort sort(array, lIndex=0, rIndex=pivot=1) # rIndex - lIndex = 1, done sort(array, lIndex=pivot + 1, rIndex=2) # lIndex == rIndex, done ``` {% endtab %} {% endtabs %} {% tabs %} {% tab title="🤖 Python3" %} ```python class Solution: def sortArray(self, nums: List[int]) -> List[int]: # return self.quickSort(nums) # return self.quickSort1(nums) return self.mergeSort(nums) def mergeSort(self, nums: List[int]) -> List[int]: # ================================================== # Array + Merge Sort = # ================================================== # time : O(nlogn) # space : O(n) def merge(left: List[int], right: List[int]) -> List[int]: ret, p1, p2 = [], 0, 0 while p1 < len(left) and p2 < len(right): if left[p1] <= right[p2]: ret += [left[p1]] p1 += 1 else: ret += [right[p2]] p2 += 1 ret += left[p1:] or right[p2:] return ret if len(nums) == 1: return nums left, right = self.mergeSort(nums[:len(nums)//2]), self.mergeSort(nums[len(nums)//2:]) return merge(left, right) def quickSort(self, nums: List[int]) -> List[int]: # ================================================== # Array + Quick Sort = # ================================================== # time : O(nlogn) # space : O(logn) def sort(nums: List[int], left: int, right: int) -> None: if right == left or right - left == 1: return pivot = partition(nums, left, right - 1) sort(nums, left, pivot) sort(nums, pivot + 1, right) def partition(nums: List[int], left: int, right: int) -> int: randomNum = (left + right) // 2 pivot = right nums[randomNum], nums[pivot] = nums[pivot], nums[randomNum] placeP = left for i in range(left, right): if nums[i] < nums[pivot]: nums[placeP], nums[i] = nums[i], nums[placeP] placeP += 1 nums[pivot], nums[placeP] = nums[placeP], nums[pivot] return placeP sort(nums, 0, len(nums)) return nums def quickSort1(self, nums: List[int]) -> List[int]: # (base case) if not nums or len(nums) == 1: return nums # ================================================== # Array + Quick Sort = # ================================================== # time : O(nlogn) # space : O(logn) pivot = nums[len(nums) // 2] lt, eq, lg = list(), list(), list() for num in nums: if num == pivot: eq += [num] elif num > pivot: lg += [num] else: lt += [num] return self.quickSort(lt) + eq + self.quickSort(lg) ``` {% endtab %} {% tab title="🤖 Java" %} ```java class Solution { public int[] sortArray(int[] nums) { return quickSort(nums); // return mergeSort(nums); } /** * @time : O(nlog(n)) * @space : O(n) */ public int[] mergeSort(int[] nums) { sortMerge(nums, 0, nums.length - 1); return nums; } private void sortMerge(int[] nums, int left, int right) { if(left < right) { int mid = (left + right) / 2; sortMerge(nums, left, mid); sortMerge(nums, mid + 1, right); merge(nums, left, mid, right); } } private void merge(int[] nums, int left, int mid, int right) { int[] ret = new int[right - left + 1]; int p0 = 0, p1 = left, p2 = mid + 1; while(p1 <= mid && p2 <= right) { if(nums[p1] < nums[p2]) ret[p0++] = nums[p1++]; else ret[p0++] = nums[p2++]; } while(p1 <= mid) ret[p0++] = nums[p1++]; while(p2 <= right) ret[p0++] = nums[p2++]; for(int i=left ; i<=right ; i++) nums[i] = ret[i - left]; } /** * @time : O(nlog(n)) * @space : O(nlog(n)) */ public int[] quickSort(int[] nums) { sortQuick(nums, 0, nums.length); return nums; } private void sortQuick(int[] nums, int left, int right) { if(left == right || right - left == 1) return; int pivot = partition(nums, left, right - 1); sortQuick(nums, left, pivot); sortQuick(nums, pivot + 1, right); } private int partition(int[] nums, int left, int right) { int randomNum = (left + right) / 2; int pivot = right; int tmp = nums[randomNum]; nums[randomNum] = nums[pivot]; nums[pivot] = tmp; int placeP = left; for(int i=left ; i