# LeetCode 912. Sort an Array

## Description

https://leetcode.com/problems/sort-an-array/

Given an array of integers `nums`, sort the array in ascending order.

Example 1:

```Input: nums = [5,2,3,1]
Output: [1,2,3,5]
```

Example 2:

```Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
```

Constraints:

• `1 <= nums.length <= 50000`
• `-50000 <= nums[i] <= 50000`

## Explanation

Use quick sort or merge sort.

## Python Solution

``````class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.quick_sort(nums, 0, len(nums) - 1)

return nums

def quick_sort(self, nums, left, right):
if left >= right:
return

pivot = self.partition(nums, left, right)
self.quick_sort(nums, left, pivot - 1)
self.quick_sort(nums, pivot + 1, right)

def partition(self, nums, left, right):

pivot = nums[right]

i = left

for j in range(left, right):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1

nums[i], nums[right] = nums[right], nums[i]

return i
``````
``````class Solution:
def sortArray(self, nums: List[int]) -> List[int]:

temps = [None for i in range(len(nums))]

self.merge_sort(nums, 0, len(nums) - 1, temps)

return nums

def merge_sort(self, nums, start, end, temps):
if start >= end:
return

mid = start + (end - start) // 2

self.merge_sort(nums, start, mid, temps)
self.merge_sort(nums, mid + 1, end, temps)

return self.merge(nums, start, mid, end, temps)

def merge(self, nums, start, mid, end, temps):

index = start

i = start
j = mid + 1

while i <= mid and j <= end:
if nums[i] <= nums[j]:
temps[index] = nums[i]
i += 1
else:
temps[index] = nums[j]
j += 1

index += 1

while i <= mid:
temps[index] = nums[i]
i += 1
index += 1

while j <= end:
temps[index] = nums[j]
j += 1
index += 1

for i in range(start, end + 1):
nums[i] = temps[i]``````
• Time complexity: O(N logN).
• Space complexity: O(N).