Problem Description

The Leetcode problem "Sort an Array" requires you to sort a given array of integers in ascending order. You are given an input array called nums, and your task is to return the sorted version of this array.

• You must sort the entire array in non-decreasing (ascending) order.
• There is only one valid solution for each input.
• You cannot reuse or duplicate elements; the result must be a permutation of the original array.
• Constraints typically include: 1 <= nums.length <= 5 * 10^4 and -5 * 10^4 <= nums[i] <= 5 * 10^4.

Your solution should efficiently sort the array and return the sorted result.

Thought Process

When tackling the "Sort an Array" problem, the most straightforward approach is to use a built-in sorting function, which is usually highly optimized. However, since this is a common interview question, it's valuable to understand how sorting algorithms work under the hood.

The brute-force approach might involve repeatedly finding the smallest element and building a new array (like selection sort), but this is inefficient for large arrays. Recognizing the inefficiency, we look for better algorithms such as Merge Sort, Quick Sort, or Heap Sort. These algorithms use divide-and-conquer or other strategies to achieve better performance.

For this problem, Merge Sort is a common choice because it guarantees O(n log n) time complexity and is stable. We can use it to demonstrate a clear, recursive, and efficient solution.

Solution Approach

We'll implement Merge Sort for this problem. Merge Sort is a classic divide-and-conquer algorithm that works as follows:

1. Divide: Split the input array into two halves.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into a single sorted array.

Why choose Merge Sort?

• It has guaranteed O(n log n) time complexity, regardless of the input's initial order.
• It is conceptually simple and easy to implement recursively.
• It does not require random access, making it suitable for linked lists as well.

The algorithm works by continually splitting the array until each subarray has one element. Then, it merges these subarrays in sorted order, building up the sorted array step by step.

Example Walkthrough

Let's walk through an example with nums = [5, 2, 3, 1]:

1. Split into two halves: [5, 2] and [3, 1]
2. Recursively split further:
   • [5, 2] → [5] and [2]
   • [3, 1] → [3] and [1]
3. Merge sorted subarrays:
   • [5] and [2] → [2, 5]
   • [3] and [1] → [1, 3]
4. Merge the results:
   • [2, 5] and [1, 3] → Compare 2 & 1, 2 & 3, 5 & 3, etc. → [1, 2, 3, 5]

At each merge step, we compare the smallest unmerged elements from each subarray and build the sorted array.

Time and Space Complexity

Brute-force (e.g., Selection Sort):

• Time Complexity: O(n²) because for each element, you scan the rest of the array to find the next smallest.
• Space Complexity: O(1) if sorting in place.

• Time Complexity: O(n log n), since each split divides the problem in half, and merging takes linear time at each level.
• Space Complexity: O(n) due to the temporary arrays used in merging.

• Time Complexity: Average O(n log n), but worst-case O(n²) if the pivot choices are poor.
• Space Complexity: O(log n) for recursion stack (in-place version).

Summary

The "Sort an Array" problem is a classic exercise in algorithm design and analysis. While built-in sorting functions are efficient, implementing your own sort (like Merge Sort) helps you understand the principles of divide-and-conquer and time complexity. Merge Sort is a reliable and efficient choice, especially for large datasets, and its step-by-step merging process ensures that the array is sorted correctly and efficiently.

Code Implementation

class Solution:
    def sortArray(self, nums):
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr
            mid = len(arr) // 2
            left = merge_sort(arr[:mid])
            right = merge_sort(arr[mid:])
            return merge(left, right)
        
        def merge(left, right):
            merged = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    merged.append(left[i])
                    i += 1
                else:
                    merged.append(right[j])
                    j += 1
            merged.extend(left[i:])
            merged.extend(right[j:])
            return merged
        
        return merge_sort(nums)
      

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
private:
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    void merge(vector<int>& nums, int left, int mid, int right) {
        vector<int> temp;
        int i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) temp.push_back(nums[i++]);
            else temp.push_back(nums[j++]);
        }
        while (i <= mid) temp.push_back(nums[i++]);
        while (j <= right) temp.push_back(nums[j++]);
        for (int k = 0; k < temp.size(); ++k) {
            nums[left + k] = temp[k];
        }
    }
};
      

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) temp[k++] = nums[i++];
            else temp[k++] = nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
        for (int x = 0; x < temp.length; x++) {
            nums[left + x] = temp[x];
        }
    }
}
      

var sortArray = function(nums) {
    function mergeSort(arr) {
        if (arr.length <= 1) return arr;
        let mid = Math.floor(arr.length / 2);
        let left = mergeSort(arr.slice(0, mid));
        let right = mergeSort(arr.slice(mid));
        return merge(left, right);
    }
    function merge(left, right) {
        let merged = [];
        let i = 0, j = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                merged.push(left[i++]);
            } else {
                merged.push(right[j++]);
            }
        }
        return merged.concat(left.slice(i)).concat(right.slice(j));
    }
    return mergeSort(nums);
};