In this guide, you will get 912. Sort an Array LeetCode Solution with the best time and space complexity. The solution to Sort an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
private:
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r)
return;
const int m = (l + r) / 2;
mergeSort(nums, l, m);
mergeSort(nums, m + 1, r);
merge(nums, l, m, r);
}
void merge(vector<int>& nums, int l, int m, int r) {
vector<int> sorted(r - l + 1);
int k = 0; // sorted's index
int i = l; // left's index
int j = m + 1; // right's index
while (i <= m && j <= r)
if (nums[i] < nums[j])
sorted[k++] = nums[i++];
else
sorted[k++] = nums[j++];
// Put the possible remaining left part into the sorted array.
while (i <= m)
sorted[k++] = nums[i++];
// Put the possible remaining right part into the sorted array.
while (j <= r)
sorted[k++] = nums[j++];
copy(sorted.begin(), sorted.end(), nums.begin() + l);
}
}; /* code provided by PROGIEZ */
912. Sort an Array LeetCode Solution in Java
class Solution {
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] nums, int l, int r) {
if (l >= r)
return;
final int m = (l + r) / 2;
mergeSort(nums, l, m);
mergeSort(nums, m + 1, r);
merge(nums, l, m, r);
}
private void merge(int[] nums, int l, int m, int r) {
int[] sorted = new int[r - l + 1];
int k = 0; // sorted's index
int i = l; // left's index
int j = m + 1; // right's index
while (i <= m && j <= r)
if (nums[i] < nums[j])
sorted[k++] = nums[i++];
else
sorted[k++] = nums[j++];
// Put the possible remaining left part into the sorted array.
while (i <= m)
sorted[k++] = nums[i++];
// Put the possible remaining right part into the sorted array.
while (j <= r)
sorted[k++] = nums[j++];
System.arraycopy(sorted, 0, nums, l, sorted.length);
}
} // code provided by PROGIEZ
912. Sort an Array LeetCode Solution in Python
class Solution:
def sortArray(self, nums: list[int]) -> list[int]:
self._mergeSort(nums, 0, len(nums) - 1)
return nums
def _mergeSort(self, nums: list[int], l: int, r: int) -> None:
if l >= r:
return
def merge(nums: list[int], l: int, m: int, r: int) -> None:
sorted = [0] * (r - l + 1)
k = 0 # sorted's index
i = l # left's index
j = m + 1 # right's index
while i <= m and j <= r:
if nums[i] < nums[j]:
sorted[k] = nums[i]
k += 1
i += 1
else:
sorted[k] = nums[j]
k += 1
j += 1
# Put the possible remaining left part into the sorted array.
while i <= m:
sorted[k] = nums[i]
k += 1
i += 1
# Put the possible remaining right part into the sorted array.
while j <= r:
sorted[k] = nums[j]
k += 1
j += 1
nums[l:l + len(sorted)] = sorted
m = (l + r) // 2
self._mergeSort(nums, l, m)
self._mergeSort(nums, m + 1, r)
merge(nums, l, m, r) # code by PROGIEZ
