Quick Sort or Count Sort? Why even choose? Let's have both. C++ 47 ms.
Intuition\nOn top of sorting algorithms there are two fundamentally different approaches:\n1. Count sort: O(n + r) time, O(r) space.\n2. Quick sort: O(n \times 
# Intuition\nOn top of sorting algorithms there are two fundamentally different approaches:\n1. Count sort: $$O(n + r)$$ time, $$O(r)$$ space.\n2. Quick sort: $$O(n \\times log(n))$$ time, $$O(1)$$ space.\nwhere $$n$$ is the number of elements to sort, and $$r$$ is the range between the minimal and the maximal elements.\n\nHere we consider both of them.\n\n# Approach\n## 1. Count Sort\nThe main idea is to use each element as an index to an ordered collection, where the number of that element\'s occurences is accumulated. The simplest approach is to use an array for that.\nConsider the following input data of $$9$$ elements:\n| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |\n|-|-|-|-|-|-|-|-|-|-|\n| Element |10|20|30|1000|-8|-1|20|30|20|\n\nThe range (which corresponds to $$r$$ parameter introduced earlier) is $$(1000-(-8)+1)=1009$$ elements long. So we allocate a `count` array of this size:\n| Index | 0 | 1 | 2 | 3 | ... | 1008 |\n|-|-|-|-|-|-|-|\n\nWe go through the input data and use each element as an index into this array. Since the array indexes are zero-based, and the input values are not, we add a bias which is the negated minimal value ($$-8$$ in this case):\n```\ncounts[10 + bias] += 1;\ncounts[20 + bias] += 1;\ncounts[30 + bias] += 1;\ncounts[1000 + bias] += 1;\n...\n```\nSo we end up with the `count` array populated as follows:\n| Index | 0 | 1 | ... | 7 | ... | 18 | ... | 28 | ... | 38 | ... | 1007 | 1008 |\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n| Value$$^1$$ | -8 | -7 | ... | -1 | ... | 10 | ... | 20 | ... | 30 | ... | 999 | 1000 |\n| Count | 1 | 0 | ... | 1 | ... | 1 | ... | 3 | ... | 2 | ... | 0 | 1 |\n\n$$^1$$"Value" row contains the original unbiased values - these are not stored, but calculated based on index.\n\nHowever, in order to determine the bias this way, we need to scan the entire input array up front. To avoid this, we can use a fixed bias corresponding to the minimal element possible ($$-50000$$ for this task).\n\nThe underlying data type of the `counter` array should be chosen to fit numbers up to `n` (for the worst case of the input array consisting of `n` times a single value). For this particular task $$n$$ does not exceed $$50000$$, so a 16 bit `unsigned short` is just fine. If we knew for sure that the number of duplicates may not exceed a certain value (e.g. $$255$$), then we would be able to choose a smaller data type (in this case, an `unsigned byte`).\n\nFinally, we walk through the `count` array and add elements corresponding to the array indexes to the result array so many times that is the `count` array element\'s value (if it\'s $$0$$ then we don\'t add the element):\n```\nfor (int i = min_value; i <= max_value; i++)\n    result.insert(result.end(), count[i], i - bias);\n```\nE.g. each of $$-8$$, $$-1$$, $$10$$ will be added $$1$$ time, $$20$$ will be added $$3$$ times, etc. So we end up with the following result vector:\n| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |\n|-|-|-|-|-|-|-|-|-|-|\n| Element |-8|-1|10|20|20|20|30|30|1000|\n\nThe key advantage of this algorithm is that for range sizes bounded by a linear function of $$n$$ it sorts the array in linear time and space: $$O(n)$$. If the range is less than linear (e.g. constant or logarithmic), then the time stays linear, but the space also decreases to become constant or logarithmic.\n\nThe major disadvantage is that, if the range is too large compared to $$n$$, then the time becomes $$O(r)$$, as is the temporary space required. Consider the input data from the example above. It has only 9 elements, but we have to allocate temporary space for 1009 counters for sorting. There are techniques for dealing with it, but they take us away from the linear time and space anyway.\n\n## 2. Quick Sort\n\nThe main idea of the quick sort (aka Hoare sort) algorithm is divide and conquer. The array is recursively split approximately in halves and each half sorted separately until the size of the chunk becomes $$1$$, which means it is already sorted. This is typically implemented in two parts: partitioning and sorting.\n\nThe sorting part is always simple:\n```\nvoid quicksort(It begin, It end) {\n    if (begin + 1 < end) {\n        It p = partition(begin, end) + 1;\n        quicksort(begin, p);\n        quicksort(p, end);\n    }\n}\n```\n(where `It` is the iterator type, `begin` points to the first element of the sorted range, and `end` points past the last element of it)\n\nThe complicated part is partitioning, i.e. dividing the range to (preferrably) equal parts. There are a number of partitioning schemes (Lomuto, Hoare, etc), described here to some level of detail: https://en.wikipedia.org/wiki/Quicksort. We are not going to dive deeply into this topic, but just pick the Hoare scheme.\n\nThe partitioning algorithm picks a pivot value from the range and moves elements less than or equal to pivot to the left part of the range and elements greater than pivot to the right part of the array. The index of the pivot value dividing the two parts is then returned. Consider our previous example:\n| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |\n|-|-|-|-|-|-|-|-|-|-|\n| Element |10|20|30|1000|-8|-1|20|30|20|\n\nSuppose we take $$20$$ as the pivot value. Then we move elements as follows:\n| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |\n|-|-|-|-|-|-|-|-|-|-|\n| Element |10|20|20|20|-8|**-1**|1000|30|30|\n\nAnd the index of the last element not exceeding $$20$$ is returned. This is the element $$-1$$ at the index $$5$$. So we see that the partitioning can be unequal, $$6$$ vs $$3$$ elements in this case. And if we took $$-8$$ as pivot, then partitioning would be even worse: $$1$$ vs $$8$$ elements. Whatever the split-up is, we proceed to sorting each part individually.\n\nHoare sort ensures $$O(n^2)$$ complexity in worst case (e.g. when pivot is consistently chosen badly, or if the entire array consists of just one repeated value).\nFor uniformly distributed random data it performs the full scan of the array $$log(n)$$ times, thus giving $$O(n \\times log(n))$$ time complexity. Generally, for more equal partitioning less number of operations is performed, ideally targeting $$n \\times log_2(n)$$. The logarithm base is a constant factor sensitive to the pivot choice and the number of repeating elements in the input data. This dependency is a major disadvantage of the algorithm (remember, the count sort does not care about duplicates or pivot choice at all).\n\nThe advantanges of the quick sort over the count sort are that it does not depend on the range of elements (apart from being sensitive to duplicates), and that it uses a constant space.\n\n## 3. Choice between Algorithms\n\nSo we have two algorithms, each of which is more efficient in certain circumstances than the other. How to we choose between them?\n\nIf we need to minimize the temporary space used, then we obviously go for the Hoare algorithm. But if we aim at the fastest sort possible, then the choice is a bit tricky. Let\'s compare the numbers of operations.\n\n| Count Sort | Quick Sort |\n|-|-|\n| $$n + r$$ | $$n \\times log_2(n)$$ |\n\nIf we try to determine the exact range before making a decision, then we have to take a single pass through the input array any way. If $$n > r$$, then we go for the count sort. Otherwise we compare $$r$$ vs $$n \\times log_2(n)$$. This is an irrational equation for the watermark, and its root can be approximated as follows (considering that $$r > n$$):\n$$n_w \\leq \\frac12(r + \\frac r {log_2(r)})$$\nand\n$$log_2(r) \\leq clz(r)$$\nwhere $$clz(r)$$ (Count Leading Zeroes) is the position of the highest $$1$$ bit in $$r$$.\nSo if $$n < n_w$$, then we go for the quick sort, otherwise we choose the count sort.\n\nHowever, the preliminary scan wastes our valuable CPU cycles, because we don\'t need it if we choose the quick sort. Can we somehow determine $$r$$ without going through the entire array?\n\nIn general, we cannot. But we can get the idea of $$r$$ by picking a random two or more elements from the array, looking at their dispersion and multiplying it by some ratio. We have chosen this approach. The main idea here is to avoid obvious pitfalls like using quick sort for an array of thousands of $$2$$\'s (there is a real test case like this) or count sort for an array of two elements $$-50000$$ and $$50000$$, and not to pay too much attention to the choice when algorithms perform roughly equal.\n\nAlternatively, we could leave the initial array traversal in place, combining it with the first partitioning round for quick sort.\n\n## Micro-optimizations\n\nThese are pretty standard:\n1. Disabling sync with `stdio` (not included here for brevity).\n1. Sorting the input vector in place in both algorithms and returning a reference to it (not its copy as LC suggests).\n1. Using a static array for counting to avoid memory allocation/deallocation.\n1. Unrolling the loop through the `count` array 4 times and aligning its boundaries, so it operates 64-bit aligned integers.\n1. Zeroing the `count` array elements just passed while they are still in cache, and while we know where they are, so we don\'t have to zero the entire array during the next test case execution.\n1. Using STL for element insertions - these might be bundled into faster 64- or 128-bit memory writes.\n\n# Complexity\n- Time complexity: pretending to be $$O(min(n + r, n \\times log_2(n)))$$, but may actually differ because we use heuristics, not the exact information, for the algorithm choice.\n\n- Space complexity: $$O(R)$$ where $$R = 5 \\times 10^4 - (-5 \\times 10^4) + 1 + alignment = $$ since we allocate a static array.\n\n# Measurements\n\n| Language | Time | Beating | Memory | Beating |\n|-|-|-|-|-|\n| C++ | 47 ms | 100% | 67.2 Mb | 69.91% |\n\nThe previous record of the execution time was somewhere below 54 ms (since my less optimized 54 ms attempt wasn\'t showing 100%).\nThe memory usage is high because of the count sorting array ($$200 Kbytes$$ + LC runtime overhead), but that\'s the cost we have to take if we want $$O(n)$$ sorting.\n\nSo we see that the solution outpeforms both the count sort-based and linear-logarithmic sort-based solutions by choosing the most appropriate one for each particular input data set. Probably a faster execution can be achieved by tuning heuristics or applying a different logic for the algorithm choice.\n\n# Code\n``` C++ []\nclass Solution {\nprivate:\n    static constexpr int MINV = -50000, MAXV = 50000;\n    static constexpr unsigned RANGEV = ((MAXV - MINV) & -4) + 4;\n\n    static unsigned short counts[RANGEV];\n\n    template <class It>\n    static It partition(It begin, It end) {\n        end--;\n        const auto pivot = *(begin + (end - begin) / 2);\n        while (true) {\n            while (*begin < pivot) begin++;\n            while (*end > pivot) end--;\n            if (begin >= end) return end;\n            swap(*begin++, *end--);\n        }\n    }\n\n    template <class It>\n    static void quicksort(It begin, It end) {\n        if (begin + 1 < end) {\n            auto p = partition(begin, end) + 1;\n            quicksort(begin, p);\n            quicksort(p, end);\n        }\n    }\n\npublic:\n    vector<int> &sortArray(vector<int>& nums) {\n        const unsigned n = nums.size();\n        if (n == 1) return nums;\n        int r = min(MAXV - MINV + 1, abs(nums.front() - nums.back()) * 2);\n        if (r > 1 && n < (r + r / (31 - __builtin_clz(r))) / 2) {\n            quicksort(nums.begin(), nums.end());\n        } else {\n            int minv = MAXV, maxv = MINV;\n            for (int v : nums) {\n                counts[v - MINV]++;\n                if (minv > v) minv = v;\n                if (maxv < v) maxv = v;\n            }\n            nums.erase(nums.begin(), nums.end());\n            const int mina = ((minv - MINV) & -4) + MINV,\n                    maxa = ((maxv - MINV - 1) & -4) + 4 + MINV;\n            for (int i = mina; i <= maxa; i += 4) {\n                nums.insert(nums.end(), counts[i - MINV], i);\n                nums.insert(nums.end(), counts[i - MINV + 1], i + 1);\n                nums.insert(nums.end(), counts[i - MINV + 2], i + 2);\n                nums.insert(nums.end(), counts[i - MINV + 3], i + 3);\n                *reinterpret_cast<long long*>(counts + (i - MINV)) = 0;\n            }\n        }\n        return nums;\n    }\n};\n\nunsigned short Solution::counts[RANGEV];\n```
['Array', 'Divide and Conquer', 'Sorting', 'Quickselect', 'Counting Sort', 'C++']