Leetcode 912. Sort an Array
Problem Explanation
The problem requires us to sort an array in ascending order. Sorting is a fundamental concept in the field of computer science. Various sorting algorithms with different time and space complexities exist. For simplifying this problem, we are going to use the "Merge Sort" algorithm.
The Merge Sort algorithm works on the principle of "Divide and Conquer". It breaks down the array into smaller sub-arrays until each sub-array consists of a single element. Then, the algorithm merges these sub-arrays to produce sorted arrays until we get a completely sorted array.
For example, consider the list [5, 1, 1, 2, 0, 0]:
Using Merge Sort, we break it down like this:
[5, 1, 1, 2] and [0, 0] -> [5, 1] [1, 2] and [0] [0] -> now we have each element in its own array.
When we merge it back together:
[1,5] [1,2] and [0] [0] -> [1, 1, 2, 5] and [0,0] -> [0, 0, 1, 1, 2, 5] (Final Sorted array)
Solution
Now, let's translate our approach into code for various languages.
1 2python 3# Python Solution 4class Solution: 5 def sortArray(self, nums: List[int]) -> List[int]: 6 # This uses python built in sort function 7 # This function uses Tim Sort Algorithm 8 return sorted(nums)
Java Solution
1
2java
3import java.util.Arrays;
4class Solution {
5 public int[] sortArray(int[] nums) {
6 // This uses java built in sort function
7 // This function uses Tim Sort Algorithm
8 Arrays.sort(nums);
9 return nums;
10 }
11}
JavaScript Solution
1 2javascript 3var sortArray = function(nums) { 4 // This uses javascript built in sort function 5 // This function uses Tim Sort Algorithm 6 return nums.sort((a, b) => a - b); 7};
C++ Solution
1
2cpp
3class Solution {
4public:
5 vector<int> sortArray(vector<int>& nums) {
6 sort(nums.begin(), nums.end());
7 return nums;
8 }
9};
C# Solution
1
2csharp
3public class Solution {
4 public int[] SortArray(int[] nums) {
5 Array.Sort(nums);
6 return nums;
7 }
8}
Though these solutions aren't implementing merge sort, as was initially present in the problem explanation, the functions used in these solutions- Python's sorted(), Java, C++ and C#'s sort(), and JS sort()- typically use variants of quicksort, heapsort, and merge sort. They are all comparison sorts, and thus can't perform better than O(n log n), but that's still considered very efficient, particularly since these functions are also optimized for space complexity.
It's often more practical to use built-in sorting functions like these for simple sorting needs, rather than to manually implement sorting algorithms. However, understanding the logic behind sorting algorithms like Merge Sort is crucial because more complex problems may require custom sorting solutions.
To implement the Merge sort algorithm, one could structure the algorithm into two main functions โ merge_sort
and merge
. merge_sort
function would recursively split the array until the base case is reached. On the other hand, merge
would take care of merging and sorting the smaller arrays.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.