All 15 sorting methods solution is here_
\nTable of Content:\nSTL\nMethod1: Standard\nMethod2: Stable\nInsertion Sort\nMethod1: Iterative\nMethod2: Recursive\nSelection Sort\nMethod1: Standard\nMethod2
```\nTable of Content:\nSTL\nMethod1: Standard\nMethod2: Stable\nInsertion Sort\nMethod1: Iterative\nMethod2: Recursive\nSelection Sort\nMethod1: Standard\nMethod2: Standard using inbuilt\nBubble Sort\nQuick Sort\nMethod1: Standard\nMethod2: Randomised\nMerge Sort\nMethod1: Outplace Merging\nMethod2: Inplace Merging\nGeneralised Radix Sort\nMethod1: Using MinVal\nMethod2: Using Partitioning\nGeneralised Counting Sort\nHeap Sort\nBucket Sort\nSTL\nMethod1: Standard (Accepted) [T(n) = O(n * lgn)]\nvoid stlSort(vector<int>& nums) {\n\tsort(nums.begin(), nums.end());\n}\nMethod2: Stable (Accepted) [T(n) = O(n * lgn)]\nvoid stableStlSort(vector<int>& nums) {\n\tstable_sort(nums.begin(), nums.end());\n}\nInsertion Sort\nMethod1: Iterative (TLE) [T(n) = O(n^2)]\nvoid insertionSort(vector<int> &nums) {\n\tint sortedInd, unsortedInd, key, size = nums.size();\n\tif (size <= 1) return;\n\tfor (unsortedInd = 1; unsortedInd < size; unsortedInd++) {\n\t\tkey = nums[unsortedInd], sortedInd = unsortedInd;\n\t\twhile (--sortedInd >= 0 and key < nums[sortedInd])\n\t\t\tnums[sortedInd + 1] = nums[sortedInd];\n\t\tnums[sortedInd + 1] = key;\n\t}\n}\nMethod2: Recursive (TLE) [T(n) = O(n^2)]\nvoid recInsert(vector<int> &nums, int val) {\n\tif (!nums.size() or nums.back() <= val)\n\t\treturn nums.push_back(val);\n\tint last = nums.back();\n\tnums.pop_back();\n\trecInsert(nums, val);\n\tnums.push_back(last);\n}\n\t\nvoid recInsertionSort(vector<int> &nums) {\n\tif (nums.size() <= 1) return;\n\tint last = nums.back();\n\tnums.pop_back();\n\trecInsertionSort(nums);\n\trecInsert(nums, last);\n}\nSelection Sort\nMethod1: Standard (TLE) [T(n) = Theta(n^2)]\nvoid selectionSort(vector<int> &nums) {\n\tint minInd, startInd, currInd, size = nums.size();\n\tif (size <= 1) return;\n\tfor (startInd = 0; startInd < size - 1; startInd++) {\n\t\tfor (currInd = startInd + 1, minInd = startInd; currInd < size; currInd++)\n\t\t\tif (nums[minInd] > nums[currInd])\n\t\t\t\tminInd = currInd;\n\t\tif (minInd != startInd)\n\t\t\tswap(nums[startInd], nums[minInd]);\n\t}\n}\nMethod2: Standard using inbuilt (TLE) [T(n) = Theta(n^2)]\nvoid selectionSort(vector<int> &nums) {\n\tint minInd, startInd, size = nums.size();\n\tif (size <= 1) return;\n\tfor (startInd = 0; startInd < size - 1; startInd++) {\n\t\tminInd = min_element(nums.begin() + startInd, nums.end()) - nums.begin();\n\t\tif (minInd != startInd)\n\t\t\tswap(nums[startInd], nums[minInd]);\n\t}\n}\nBubble Sort (TLE) [T(n) = Theta(n^2)]\nvoid bubbleSort(vector<int> &nums) {\n\tint endInd, currInd, size = nums.size();\n\tif (size <= 1) return;\n\tfor (endInd = size - 1; endInd; endInd--)\n\t\tfor (currInd = 0; currInd < endInd; currInd++)\n\t\t\tif (nums[currInd] > nums[currInd + 1])\n\t\t\t\tswap(nums[currInd], nums[currInd + 1]);\n}\nQuick Sort\nMethod1: Standard (TLE) [T(n) = O(n^2)]\nint partitionArray(vector<int> &nums, int low, int high) {\n\tif (low >= high) return -1;\n\tint pivot = low, l = pivot + 1, r = high;\n\twhile (l <= r)\n\t\tif (nums[l] < nums[pivot]) l++;\n\t\telse if (nums[r] >= nums[pivot]) r--;\n\t\telse swap(nums[l], nums[r]);\n\tswap(nums[pivot], nums[r]);\n\treturn r;\n}\n\t\nvoid quickSort(vector<int> &nums, int low, int high) {\n\tif (low >= high) return;\n\tint pivot = partitionArray(nums, low, high);\n\tquickSort(nums, low, pivot);\n\tquickSort(nums, pivot + 1, high);\n}\nMethod2: Randomised (Accepted) [T(n) = O(n * lgn)]\nint partitionArray(vector<int> &nums, int low, int high) {\n\tif (low >= high) return -1;\n\tint pivot = low, l = pivot + 1, r = high;\n\twhile (l <= r)\n\t\tif (nums[l] < nums[pivot]) l++;\n\t\telse if (nums[r] >= nums[pivot]) r--;\n\t\telse swap(nums[l], nums[r]);\n\tswap(nums[pivot], nums[r]);\n\treturn r;\n}\n\nvoid quickSort(vector<int> &nums, int low, int high) {\n\tif (low >= high) return;\n\tswap(nums[low + rand() % (high - low + 1)], nums[low]);\n\tint pivot = partitionArray(nums, low, high);\n\tquickSort(nums, low, pivot);\n\tquickSort(nums, pivot + 1, high);\n}\nMerge Sort\nMethod1: Outplace Merging (Accepted) [T(n) = O(n * lgn)]\nvoid outPlaceMerge(vector<int> &nums, int low, int mid, int high) {\n\tif (low >= high) return;\n\tint l = low, r = mid + 1, k = 0, size = high - low + 1;\n\tvector<int> sorted(size, 0);\n\twhile (l <= mid and r <= high)\n\t\tsorted[k++] = nums[l] < nums[r] ? nums[l++] : nums[r++];\n\twhile (l <= mid) \n\t\tsorted[k++] = nums[l++];\n\twhile (r <= high) \n\t\tsorted[k++] = nums[r++];\n\tfor (k = 0; k < size; k++)\n\t\tnums[k + low] = sorted[k];\n}\n\nvoid mergeSort(vector<int> &nums, int low, int high) {\n\tif (low >= high) return;\n\tint mid = (high - low) / 2 + low;\n\tmergeSort(nums, low, mid);\n\tmergeSort(nums, mid + 1, high);\n\toutPlaceMerge(nums, low, mid, high);\n}\nMethod2: Inplace Merging (TLE) [T(n) = O(n^2)]\nvoid inPlaceMerge(vector<int> &nums, int low, int mid, int high) {\n\tif (low >= high) return;\n\tint l = low, r = mid + 1, size = high - low + 1;\n\twhile (l <= mid and r <= high) {\n\t\tif (nums[l] <= nums[r]) l++;\n\t\telse {\n\t\t\tint val = nums[r];\n\t\t\tfor (int k = r++; k > l; k--)\n\t\t\t\tnums[k] = nums[k - 1];\n\t\t\tnums[l++] = val;\n\t\t\tmid++;\n\t\t}\n\t}\n}\n\nvoid mergeSort(vector<int> &nums, int low, int high) {\n\tif (low >= high) return;\n\tint mid = (high - low) / 2 + low;\n\tmergeSort(nums, low, mid);\n\tmergeSort(nums, mid + 1, high);\n\tinPlaceMerge(nums, low, mid, high);\n}\nGeneralised Couting Sort (Accepted) [T(n) = Theta(max(n, m)) where m = max(Arr)]\nvoid countingSort(vector<int> &nums, bool isAscending=true) {\n\tint minVal = *min_element(nums.begin(), nums.end());\n\tint maxVal = *max_element(nums.begin(), nums.end());\n\tint freqSize = maxVal - minVal + 1 + 1, size = nums.size();\n\tvector<int> freq(freqSize, 0), sorted(size, 0);\n\tfor (int ind = 0; ind < size; ind++)\n\t\tfreq[nums[ind] - minVal]++;\n\tif (isAscending)\n\t\tfor (int ind = 1; ind < freqSize; ind++)\n\t\t\tfreq[ind] += freq[ind - 1];\n\telse\n\t\tfor (int ind = freqSize - 2; ind >= 0; ind--)\n\t\t\tfreq[ind] += freq[ind + 1];\n\t// for stable sorting start ind from end and decrement till 0\n\tfor (int ind = size - 1; ind >= 0; ind--)\n\t\tsorted[freq[nums[ind] - minVal]-- - 1] = nums[ind];\n\tnums = sorted;\n}\nGeneralised Radix Sort\nMethod1: Using MinVal (Accepted) [T(n) = Theta(n)]\nint getDigit(int num, int factor) {\n\treturn (abs(num) / abs(factor)) % 10;\n}\n\nvoid radixCountingSort(vector<int> &nums, int factor) {\n\tint freqSize = 10, size = nums.size();\n\tvector<int> freq(freqSize, 0), sorted(size, 0);\n\tfor (int ind = 0; ind < size; ind++)\n\t\tfreq[getDigit(nums[ind], factor)]++;\n\tfor (int ind = 1; ind < freqSize; ind++)\n\t\tfreq[ind] += freq[ind - 1];\n\t// for stable sorting start ind from end and decrement till 0\n\tfor (int ind = size - 1; ind >= 0; ind--)\n\t\tsorted[freq[getDigit(nums[ind], factor)]-- - 1] = nums[ind];\n\tnums = sorted;\n}\n\nvoid radixSort(vector<int> &nums) {\n\tint minVal = *min_element(nums.begin(), nums.end());\n\tfor (auto &num : nums) num -= minVal;\n\tint factor = 1, maxVal = *max_element(nums.begin(), nums.end());\n\twhile (maxVal / factor) {\n\t\tradixCountingSort(nums, factor);\n\t\tfactor *= 10;\n\t}\n\tfor (auto &num : nums) num += minVal;\n}\nMethod2: Using Partitioning (Accepted) [T(n) = Theta(n)]\n\nIdea is to partition the Array with pivot as mininum Positive Element and thus, left half array is of -ve no.s (if any) and right half array is of +ve no.s (if any). Finally we apply Radix Sort on both the parts.\nNote that to sort -ve no.s only with Radix Sort, we need to reverse sort the -ve no.s (eg: [-5,-4,-3] and [3,4,5])\n\nint partitionArray(vector<int> &nums, int low=0, int high=-1) {\n\thigh = high < 0 ? nums.size() - 1 : high;\n\tif (low >= high) return -1;\n\tint pivot = low, l = pivot + 1, r = high;\n\twhile (l <= r)\n\t\tif (nums[l] < nums[pivot]) l++;\n\t\telse if (nums[r] >= nums[pivot]) r--;\n\t\telse swap(nums[l], nums[r]);\n\tswap(nums[pivot], nums[r]);\n\treturn r;\n}\n\nint getDigit(int num, int factor) {\n\treturn (abs(num) / abs(factor)) % 10;\n}\n\npair<int, int> getMinAndNonNegMinInd(vector<int> &nums) {\n\tint minInd = nums.size(), minVal = INT_MAX;\n\tint nonNegMinInd = nums.size(), minNonNegVal = INT_MAX;\n\tfor (int i = 0; i < nums.size(); i++) {\n\t\tif (nums[i] >= 0 and nums[i] < minNonNegVal)\n\t\t\tnonNegMinInd = i, minNonNegVal = nums[i];\n\t\tif (nums[i] < minVal)\n\t\t\tminInd = i, minVal = nums[i];\n\t}\n\treturn {minInd, nonNegMinInd};\n}\n\nint radixSortPartionArray(vector<int> &nums) {\n\tauto [minInd, nonNegMinInd] = getMinAndNonNegMinInd(nums);\n\tif (nonNegMinInd < nums.size()) {\n\t\tif (nonNegMinInd) swap(nums[0], nums[nonNegMinInd]);\n\t\tif (nums[minInd] >= 0) nonNegMinInd = 0;\n\t\telse nonNegMinInd = partitionArray(nums);\n\t}\n\treturn nonNegMinInd;\n}\n\nvoid radixCountingSort(vector<int> &nums, int factor, int low, int high, bool isAscending=true) {\n\tif (low >= high) return;\n\tint freqSize = 10, size = high - low + 1;\n\tvector<int> freq(freqSize, 0), sorted(size, 0);\n\tfor (int ind = 0; ind < size; ind++)\n\t\tfreq[getDigit(nums[ind + low], factor)]++;\n\tif (isAscending)\n\t\t// reference: http://analgorithmaday.blogspot.com/2011/03/counting-sortlinear-time.html\n\t\tfor (int ind = 1; ind < freqSize; ind++)\n\t\t\tfreq[ind] += freq[ind - 1];\n\telse\n\t\tfor (int ind = freqSize - 2; ind >= 0; ind--)\n\t\t\tfreq[ind] += freq[ind + 1];\n\t// for stable sorting start ind from end and decrement till 0\n\tfor (int ind = size - 1; ind >= 0; ind--)\n\t\tsorted[freq[getDigit(nums[ind + low], factor)]-- - 1] = nums[ind + low];\n\tfor (int ind = 0; ind < size; ind++)\n\t\tnums[ind + low] = sorted[ind];\n}\n\nvoid radixSortHelper(vector<int> &nums, int low, int high, bool isAscending=true) {\n\tif (low >= high) return;\n\tint maxVal = *max_element(nums.begin() + low, nums.begin() + high + 1, [] (int &a, int &b) {\n\t\treturn abs(a) < abs(b);\n\t});\n\tint factor = 1;\n\twhile (maxVal / factor) {\n\t\tradixCountingSort(nums, factor, low, high, isAscending);\n\t\tfactor *= 10;\n\t}\n}\n\nvoid radixSort(vector<int> &nums) {\n\tint nonNegMinInd = radixSortPartionArray(nums);\n\tif (nonNegMinInd <= 1)\n\t\tradixSortHelper(nums, nonNegMinInd + 1, nums.size() - 1);\n\telse {\n\t\tradixSortHelper(nums, 0, nonNegMinInd - 1, false);\n\t\tradixSortHelper(nums, nonNegMinInd + 1, nums.size() - 1);\n\t}\n}\nHeap Sort (Accepted) [T(n) = O(n * lgn)]\nvoid heapifyDown(vector<int> &nums, int size, int rootInd, bool isMin=false) {\n\tif (size <= 1 or rootInd < 0 or rootInd >= size - 1) return;\n\tint keyInd = rootInd, leftChildInd = 2 * rootInd + 1, rightChildInd = 2 * rootInd + 2;\n\tif (leftChildInd < size and (isMin ? nums[leftChildInd] < nums[keyInd] : nums[leftChildInd] > nums[keyInd]))\n\t\tkeyInd = leftChildInd;\n\tif (rightChildInd < size and (isMin ? nums[rightChildInd] < nums[keyInd] : nums[rightChildInd] > nums[keyInd]))\n\t\tkeyInd = rightChildInd;\n\tif (nums[keyInd] != nums[rootInd]) {\n\t\tswap(nums[rootInd], nums[keyInd]);\n\t\theapifyDown(nums, size, keyInd, isMin);\n\t}\n}\n\nvoid heapifyArray(vector<int> &nums, bool isMin=false) {\n\tint size = nums.size();\n\tif (size <= 1) return;\n\tint tailRootInd = (size >> 1) - 1;\n\tfor (int rootInd = tailRootInd; rootInd >= 0; rootInd--)\n\t\theapifyDown(nums, size, rootInd, isMin);\n}\n\nvoid heapSort(vector<int> &nums) {\n\tif (nums.size() <= 1) return;\n\theapifyArray(nums);\n\tfor (int size = nums.size() - 1; size; size--) {\n\t\tswap(nums[size], nums[0]);\n\t\theapifyDown(nums, size, 0);\n\t}\n}\nBucket Sort\nBucket sort\'s performance depends upon the uniformity (distribution) of the input data. Hence, I am not discussing it here (I have not submitted it as well for given constraints). For more info on this Algo, you can google it.\n\nAmong above, Counting Sort was fastest in Leetcode OJ.\n```
['Recursion', 'C', 'Sorting', 'Heap (Priority Queue)', 'Merge Sort', 'Iterator']