Sort an Array

Leetcode Problem:

• Sort an Array

Summary

• Sort an array of integers in ascending order without using built-in O(nlog(n)) time complexity and smallest space complexity possible.

Approach

• The approach used is a modified merge sort algorithm
• The array is divided into two halves until each subarray contains only one element, and then the subarrays are merged back together in sorted order.

Complexity

• O(nlog(n))

Explain

• The solution code uses a modified merge sort algorithm to sort the array
• The merge function takes three parameters: the left index, the right index, and the current index
• It compares the elements at the left and right indices and swaps them if necessary
• The merge_sort function recursively divides the array into two halves until each subarray contains only one element, and then it merges the subarrays back together in sorted order
• The time complexity of the solution is O(nlog(n)) because the merge sort algorithm has a time complexity of O(nlog(n)) and the space complexity is O(n) because the temporary array has a size of n.

Solution Code:

class Solution {
public:
    void merge(vector& nums, int l , int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        int tmp[50001];
        while(i <= mid && j <= r){
            if (nums[i] <= nums[j]){
                tmp[cur++] = nums[i++];
            } else {
                tmp[cur++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = nums[i++];
        }
        for(i = l; i < cur; i++){
            nums[i] = tmp[i];
        }
    }
    void merge_sort(vector& nums, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid+1, r);
        merge(nums, l, mid, r);
    }
    vector sortArray(vector& nums) {
        merge_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};