Merge Sort|Radix sort|counting sort|heap sort||47ms Beats 99.41%
Intuition\n Describe your first thoughts on how to solve this problem. \n1. Try merge sort which is stable & O(n log n) time\n2. Radix sort is a stable sort wit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. Try merge sort which is stable & O(n log n) time\n2. Radix sort is a stable sort with 64 buckets with 3 passes & O(3n) time\n3.  Counting sort is very suitible for this question which can be done very quickly.\n4. Heap sort is unstable, but at worst O(n log n)\n# Approach\n<!-- Describe your approach to solving the problem. -->\nJust pratice for different implementations.\nWhy not quick sort? quick sort has at worst O(n^2); the choice of the pivot & the partition must be very careful. The textbook version for the quick sort might not pass the LC\'s testcases.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nMerge sort: O(n log n)\nRadix sort: O(3n)\nCounting sort: O(n+m) where m=max(x)-min(x)+1\nHeap sort: O(n log n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nMerge sort:O(n)\nRadix sort: O(|buckets|+n)\nCounting sort: O(m) where m=max(x)-min(x)+1\nHeap sort: O(log n) (for the recursion stack); O(1) (iterative version for heapify)\n# Code Merge Sort\n```\nclass Solution {\npublic:\n    void merge(vector<int>& A, int start, int mid, int end, vector<int>& buff)\n    {\n        int left=start, right=mid+1;\n        int s=end-start+1;\n        for(int i=0; i<s; i++)\n        {       \n            int i0=start+i;\n            if(left>mid){\n                buff[i0]=A[right];\n                right++;\n            } else if (right>end){\n                buff[i0]=A[left];\n                left++;\n            } else  if (A[left]<A[right]){\n                buff[i0]=A[left];\n                left++;\n            } else{\n                buff[i0]=A[right];\n                right++;\n            }\n        }\n        for(int i=start; i<start+s; i++) A[i]=buff[i];\n    }\n    void mergeSort(vector<int>& A, int start, int end, vector<int>& buff )\n    {\n        if(end<=start) return;\n        int mid=start+(end-start)/2;\n        mergeSort(A, start, mid, buff);\n        mergeSort(A, mid+1, end, buff);\n        merge(A, start, mid, end, buff);\n    }\n    vector<int> sortArray(vector<int>& nums) {\n        vector<int> buff(nums.size());\n        mergeSort(nums, 0, nums.size()-1 ,buff);\n        return nums;\n    }\n};\n```\n# C++ Radix sort||47ms Beats 99.41%\n```\nclass Solution {\npublic:\n    const int xmin=-5*1e4;\n    vector<int> bucket[64];//64**3=262144>1e5+1\n    void radix_sort(vector<int>& nums) {\n        // 1st round\n        for (int& x : nums){// adjust x-=xmin\n            x-=xmin;\n            bucket[x&63].push_back(x);\n        }\n        int i = 0;\n        for (auto &B : bucket) {\n            for (auto v : B)\n                nums[i++] = v;\n            B.clear();\n        }\n        // 2nd round\n        for (int& x : nums)\n            bucket[(x>>6)&63].push_back(x);\n        i=0;\n        for (auto &B : bucket) {\n            for (auto v : B)\n                nums[i++] = v;\n            B.clear();\n        }\n        // 3rd round\n        for (int& x : nums)\n            bucket[x>>12].push_back(x);\n        i=0;\n        for (auto &B : bucket) {\n            for (auto v : B)//adjust back\n                nums[i++] = v+xmin;\n        //    B.clear();\n        }\n    }\n    vector<int> sortArray(vector<int>& nums) {\n        radix_sort(nums);\n        return nums;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}(); \n```\n# C++ using counting sort||49ms Beats 99.22%\n```\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        const int vmin=-5*1e4, N=1e5+1;\n        int freq[N]={0}, xMax=-1, xmin=N;\n        for(int x:nums) {\n            x-=vmin;\n            freq[x]++;\n            xMax=max(x, xMax);\n            xmin=min(x, xmin);\n        }\n        for(int i=0, x=xmin; x<=xMax; x++){\n            int f=freq[x];\n            fill(nums.begin()+i, nums.begin()+i+f, x+vmin);//adjust back\n            i+=f;\n        }\n        return nums;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}(); \n```\n# C++ using heap sort||84ms Beats 90.20%\n```\nclass Solution {\npublic:\n    inline void heapify(vector<int>& nums, int l, int r){\n        int parent=l, child=(parent<<1)+1;\n        if (child>r) return;\n        if (child+1 <= r  && nums[child]<nums[child+1]) child++;\n        if (nums[parent]>nums[child]) return;\n        swap(nums[parent], nums[child]);\n        heapify(nums, child, r);\n    }\n    inline void heap_sort(vector<int>& nums){\n        const int n=nums.size();\n        for(int i=n/2-1; i>=0; i--)\n            heapify(nums, i, n-1);\n        for(int i=n-1; i>0; i--){\n            swap(nums[0], nums[i]);\n            heapify(nums, 0, i-1);\n        }\n    }\n    vector<int> sortArray(vector<int>& nums) {\n        heap_sort(nums);\n        return nums;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}(); \n```\n# iterative version for  heapify \n```\n    inline void heapify(vector<int>& nums, int l, int r){\n        int parent=l, child=(parent<<1)+1;\n        while (child<=r){\n            if (child+1 <= r  && nums[child]<nums[child+1]) child++;\n            if (nums[parent]>nums[child]) return;\n            else{\n                swap(nums[parent], nums[child]);\n                parent=child;\n                child=(parent<<1)+1;\n            }\n        }\n    }\n```
['Array', 'Divide and Conquer', 'Sorting', 'Heap (Priority Queue)', 'Merge Sort', 'Radix Sort', 'Counting Sort', 'C++']