Home | Projects | Notes > Problem Solving > LC - E - 912. Sort an Array

LC - E - 912. Sort an Array

Solutions in C++

Solution 1

Merge sort.

Complexity Analysis:

• T = O(n log n)

• S = O(n)

Solution:

45
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums) {
4
        // base case        
5
        if (nums.size() <= 1)
6
            return nums;
7
        
8
        int mid = nums.size() / 2;
9
        
10
        // split the original array into halves
11
        vector<int> left(nums.begin(), nums.begin() + mid);
12
        vector<int> right(nums.begin() + mid, nums.end());
13

14
        sortArray(left);
15
        sortArray(right);
16
        merge(nums, left, right);
17

18
        return nums;
19
    }
20

21
private:
22
    void merge(vector<int> &arr, const vector<int> &left, const vector<int> &right)
23
    {
24
        int i = 0;  // index for the original array
25
        int l = 0;  // index for the left subarray
26
        int r = 0;  // index for the right subarray
27

28
        // memrge elements of the two subarrays
29
        while (l < left.size() && r < right.size())
30
        {
31
            arr[i++] = (left[l] <= right[r]) ? left[l++] : right[r++];
32
        }
33

34
        // copy remaining elements (only one subarray may have leftovers)
35
        while (l < left.size())
36
        {
37
            arr[i++] = left[l++];
38
        }
39

40
        while (r < right.size())
41
        {
42
            arr[i++] = right[r++];
43
        }
44
    }
45
};