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.