912. Sort an Array

Posted on Edited on In

912. Sort an Array

Description

Difficulty: Medium

Related Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort

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(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

1
2
3
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:

1
2
3
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 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Hints/Notes

  • merge sort

Solution

Language: C++

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 {
public:
    vector<int> tmp;

    vector<int> sortArray(vector<int>& nums) {
        tmp = vector<int>(nums.size(), 0);
        sort(nums, 0, nums.size() - 1);
        return nums;
    }

    void sort(vector<int>& nums, int low, int high) {
        if (high <= low)
            return;

        int mid = low + (high - low) / 2;
        sort(nums, low, mid);
        sort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }

    void merge(vector<int>& nums, int low, int mid, int high) {
        for (int i = low; i <= high; i++) {
            tmp[i] = nums[i];
        }
        int i = low, j = mid + 1; 
        for (int index = low; index <= high; index++) {
            if (i == mid + 1) {
                nums[index] = tmp[j++];
            } else if (j == high + 1) {
                nums[index] = tmp[i++];
            } else if (tmp[i] < tmp[j]) {
                nums[index] = tmp[i++];
            } else {
                nums[index] = tmp[j++];
            }
        }
    }
};