##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/912.html

# 912. Sort an Array (Medium)

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

Example 1:

Input: [5,2,3,1]
Output: [1,2,3,5]


Example 2:

Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]


Note:

1. 1 <= A.length <= 10000
2. -50000 <= A[i] <= 50000

## Solution 1. STL

// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums;
}
};


## Solution 2. Quick Sort

// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN) on average
// Space: O(1)
class Solution {
private:
int partition(vector<int> &nums, int L, int R, int pivot) {
swap(nums[pivot], nums[R]);
for (int i = L; i < R; ++i) {
if (nums[i] >= nums[R]) continue;
swap(nums[i], nums[L++]);
}
swap(nums[L], nums[R]);
return L;
}
void quickSort(vector<int> &nums, int L, int R) {
if (L >= R) return;
int M = partition(nums, L, R, rand() % (R - L + 1) + L);
quickSort(nums, L, M - 1);
quickSort(nums, M + 1, R);
}
public:
vector<int> sortArray(vector<int>& nums) {
srand (time(NULL));
quickSort(nums, 0, nums.size() - 1);
return nums;
}
};


## Solution 3. Merge Sort

// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(N)
class Solution {
private:
vector<int> tmp;
void mergeSort(vector<int> &nums, int start, int end) {
if (start + 1 >= end) return;
int mid = (start + end) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid, end);
for (int i = start, j = mid, k = 0; i < mid || j < end; ++k) {
tmp[k] = (i >= mid || (j < end && nums[j] < nums[i])) ? nums[j++] : nums[i++];
}
for (int i = start; i < end; ++i) nums[i] = tmp[i - start];
}
public:
vector<int> sortArray(vector<int>& nums) {
tmp = vector<int>(nums.size());
mergeSort(nums, 0, nums.size());
return nums;
}
};


## Solution 4. Heap Sort

// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(1)
class Solution {
private:
void heapify(vector<int> &nums) {
for (int i = nums.size() / 2 - 1; i >= 0; --i)
siftDown(nums, i, nums.size());
}
void siftDown(vector<int> &nums, int hole, int end) {
int next = 2 * hole + 1;
while (next < end) {
if (next + 1 < end && nums[next + 1] > nums[next]) ++next;
if (nums[hole] > nums[next]) break;
swap(nums[hole], nums[next]);
hole = next;
next = 2 * next + 1;
}
}
public:
vector<int> sortArray(vector<int>& nums) {
heapify(nums);
for (int i = nums.size() - 1; i > 0; --i) {
swap(nums[0], nums[i]);
siftDown(nums, 0, i);
}
return nums;
}
};

• class Solution {
public List<Integer> sortArray(int[] nums) {
return mergeSort(nums);
}

public List<Integer> mergeSort(int[] nums) {
int length = nums.length;
if (length == 1) {
List<Integer> list = new ArrayList<Integer>();
return list;
} else {
int halfLength = length / 2;
int[] nums1 = new int[halfLength];
int[] nums2 = new int[length - halfLength];
for (int i = 0; i < halfLength; i++)
nums1[i] = nums[i];
for (int i = halfLength; i < length; i++)
nums2[i - halfLength] = nums[i];
List<Integer> list1 = mergeSort(nums1);
List<Integer> list2 = mergeSort(nums2);
return merge(list1, list2);
}
}

public List<Integer> merge(List<Integer> list1, List<Integer> list2) {
List<Integer> mergedList = new ArrayList<Integer>();
int size1 = list1.size(), size2 = list2.size();
int index1 = 0, index2 = 0;
while (index1 < size1 && index2 < size2) {
int num1 = list1.get(index1), num2 = list2.get(index2);
if (num1 <= num2) {
index1++;
} else {
index2++;
}
}
while (index1 < size1) {
index1++;
}
while (index2 < size2) {
index2++;
}
return mergedList;
}
}

############

class Solution {
private int[] nums;

public int[] sortArray(int[] nums) {
this.nums = nums;
quikcSort(0, nums.length - 1);
return nums;
}

private void quikcSort(int l, int r) {
if (l >= r) {
return;
}
int x = nums[(l + r) >> 1];
int i = l - 1, j = r + 1;
while (i < j) {
while (nums[++i] < x) {
}
while (nums[--j] > x) {
}
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
quikcSort(l, j);
quikcSort(j + 1, r);
}
}

• // OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums;
}
};

• class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quick_sort(l, r):
if l >= r:
return
x = nums[randint(l, r)]
i, j, k = l - 1, r + 1, l
while k < j:
if nums[k] < x:
nums[i + 1], nums[k] = nums[k], nums[i + 1]
i, k = i + 1, k + 1
elif nums[k] > x:
j -= 1
nums[j], nums[k] = nums[k], nums[j]
else:
k = k + 1
quick_sort(l, i)
quick_sort(j, r)

quick_sort(0, len(nums) - 1)
return nums


• func sortArray(nums []int) []int {
quickSort(nums, 0, len(nums)-1)
return nums
}

func quickSort(nums []int, l, r int) {
if l >= r {
return
}
i, j := l-1, r+1
x := nums[(l+r)>>1]
for i < j {
for {
i++
if nums[i] >= x {
break
}
}
for {
j--
if nums[j] <= x {
break
}
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
quickSort(nums, l, j)
quickSort(nums, j+1, r)
}

• function sortArray(nums: number[]): number[] {
function quickSort(l: number, r: number) {
if (l >= r) {
return;
}
let i = l - 1;
let j = r + 1;
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
}


• /**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function (nums) {
function quickSort(l, r) {
if (l >= r) {
return;
}
let i = l - 1;
let j = r + 1;
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
quickSort(l, j);
quickSort(j + 1, r);
}
const n = nums.length;
quickSort(0, n - 1);
return nums;
};