912. Sort an Array

• Merge Sort

class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void merge(vector<int> &nums, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        vector<int> l1(n1), l2(n2);
        for (int i = 0; i < n1; ++i) l1[i] = nums[left + i];

        for (int i = 0; i < n2; ++i) l2[i] = nums[mid + 1 + i];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
        {
            if (l1[i] <= l2[j])
            {
                nums[k] = l1[i++];
            }
            else
            {
                nums[k] = l2[j++];
            }
            ++k;
        }

        while (i < n1)
        {
            nums[k] = l1[i];
            ++i; ++k;
        }

        while (j < n2)
        {
            nums[k] = l2[j];
            ++j; ++k;
        }
    }

    void mergeSort(vector<int> &nums, int left, int right)
    {
     if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
};

• T: $O(n \log n)$

• S: $O(1)$

• Quick Sort (TLE)

class Solution {
public:
    vector<int> sortArray(vector<int>& nums)
    {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return

        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    int partition(vector<int>& nums, int left, int right)
    {
        int pivot = nums[right];
        int pointer = left;
        for (int i = left; i < right; ++i)
        {
            if (nums[i] <= pivot)
            {
                swap(nums[pointer++], nums[i]);
            }
        }
        swap(nums[pointer], nums[right]);
        return pointer;
    }
};

• T: $O(n \log n)$
• S: $O(1)$