Skip to content

Sort an Array⚓︎

Link

Description⚓︎

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in \(O(n\log n)\) time complexity and with the smallest space complexity possible.

Example 1:

  • Input: nums = [5,2,3,1]
  • Output: [1,2,3,5]
  • Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

  • Input: nums = [5,1,1,2,0,0]
  • Output: [0,0,1,1,2,5]
  • Explanation: Note that the values of nums are not necessairly unique.

Constraints:

  • 1 <= nums.length <= 5 * 10^4
  • -5 * 10^4 <= nums[i] <= 5 * 10^4

Solution⚓︎

Merge Sort⚓︎

Recursive Version⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
private:
    vector<int> temp;

    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;

        int mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        mergeOperation(nums, left, mid, right);
    }

    void mergeOperation(vector<int>& nums, int left, int mid, int right) {
        int k = 0, i = left, j = mid + 1;
        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 (i = left, j = 0; i <= right; i++, j++) nums[i] = temp[j];
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        temp.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};
  • Time complexity: \(O(n\log n)\);
  • Space complexity: \(O(\log n)\) for recursive approach.

Iterative Version⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
private:
    vector<int> temp;

    void mergeSort(vector<int>& nums) {
        int n = nums.size();
        for (int left, mid, right, step = 1; step < n; step <<= 1) {
            left = 0;
            while (left < n) {
                mid = left + step - 1;
                if (mid + 1 >= n) break;
                right = min(left + (step << 1) - 1, n - 1);
                mergeOperation(nums, left, mid, right);
                left = right + 1;
            }
        }
    }

    void mergeOperation(vector<int>& nums, int left, int mid, int right) {
        int k = 0, i = left, j = mid + 1;
        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 (i = left, j = 0; i <= right; i++, j++) nums[i] = temp[j];
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        temp.resize(nums.size());
        mergeSort(nums);
        return nums;
    }
};

Quick Sort⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    void quick_sort(vector<int>& nums, int l, int r) {
        if (l == r) return;
        int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(nums[i], nums[j]);
        }
        quick_sort(nums, l, j);
        quick_sort(nums, j + 1, r);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};
  • Time complexity: average case \(O(n\log n)\), worst case \(O(n^2)\) (but we rarely reach the worst case);
  • Space complexity: \(O(\log n)\).

Heap Sort⚓︎

STL Version⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> q;
        vector<int> res;
        res.reserve(nums.size());
        for (int i : nums) q.push(i);
        while (!q.empty()) {
            res.emplace_back(q.top());
            q.pop();
        }
        return res;
    }
};

Array Version⚓︎

Min Heap⚓︎
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
private:
    vector<int> h;
    int cnt;

    void up(int u) {
        if (u / 2 && h[u / 2] > h[u]) {
            swap(h[u], h[u / 2]);
            up(u / 2);
        }
    }

    void down(int u) {
        int v = u;
        if (2 * u <= cnt && h[2 * u] < h[v]) v = 2 * u;
        if (2 * u + 1 <= cnt && h[2 * u + 1] < h[v]) v = 2 * u + 1;
        if (u != v) {
            swap(h[u], h[v]);
            down(v);
        }
    }

    void push(int x) {
        h[++cnt] = x;
        up(cnt);
    }

    void pop() {
        h[1] = h[cnt--];
        down(1);
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        h = vector<int>(n + 1, 0);
        cnt = nums.size();
        for (int i = 1; i <= n; i++) h[i] = nums[i - 1];
        for (int i = n / 2; i; i--) down(i);

        vector<int> res;
        res.reserve(n);
        while (n--) {
            res.emplace_back(h[1]);
            pop();
        }
        return res;
    }
};
Max Heap⚓︎

Iterative Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
private:
    // Adjust the number at position i upwards to maintain the max heap
    // arr[i] = x, x is new! Look upwards until it's no longer larger than its parent, or reaches the top (0 position)
    void heapInsert(vector<int>& nums, int i) {
        while (nums[i] > nums[(i - 1) / 2]) {
            swap(nums[i], nums[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    // The number at position i has decreased, but we still want to maintain the max heap structure
    // Adjust downwards to maintain the max heap
    // The current size of the heap is "size"
    void heapify(vector<int>& nums, int i, int size) {
        int left = 2 * i + 1;
        while (left < size) {
            // There's a left child, left
            // and a right child, left + 1
            // Choose the "stronger" child
            int largest = (left + 1 < size && nums[left + 1] > nums[left]) ? left + 1 : left;
            // After choosing the "stronger" child, 
            // compare the current number with the strongest child to find the largest index
            largest = nums[largest] > nums[i] ? largest : i;
            if (largest == i) break;
            swap(nums[i], nums[largest]);
            i = largest;
            left = 2 * i + 1;
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> arr = nums;
        int n = arr.size();
        // Method 1: builds the heap from top to bottom and then sorts
        // Build a max heap from top to bottom, O(n * logn)
        // Sequentially pop the maximum value in the heap and sort, O(n * logn)
        // Overall time complexity O(n * logn)
        // for (int i = 0; i < n; i++) {
        //     heapInsert(arr, i);
        // }

        // Method 2: builds the heap from bottom to top and then sorts
        // Build a max heap from bottom to top, O(n)
        // Sequentially pop the maximum value in the heap and sort, O(n * logn)
        // Overall time complexity O(n * logn)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }

        int size = n;
        while (size > 1) {
            swap(arr[0], arr[--size]);
            heapify(arr, 0, size);
        }
        return arr;
    }
};

Recursive Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
private:
    void heapInsert(vector<int>& nums, int i) {
        if (i == 0) return;
        int parent = (i - 1) / 2;
        if (nums[i] > nums[parent]) {
            swap(nums[i], nums[parent]);
            heapInsert(nums, parent);
        }
    }

    void heapify(vector<int>& nums, int i, int size) {
        int left = 2 * i + 1, right = 2 * i + 2, largest = i;
        if (left < size && nums[left] > nums[largest]) largest = left;
        if (right < size && nums[right] > nums[largest]) largest = right;
        if (largest != i) {
            swap(nums[i], nums[largest]);
            heapify(nums, largest, size);
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> arr = nums;
        int n = arr.size();
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, i, n);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            heapify(arr, 0, i);
        }
        return arr;
    }
};