C++ Clean Code Solution | Fastest | All (15+) Sorting Methods | Detailed
Table of Content:\n STL\n\t Method1: Standard \n\t Method2: Stable\n Insertion Sort\n\t Method1: Iterative\n\t Method2: Recursive\n Selection Sort\n\t Method1: 
### Table of Content:\n* STL\n\t* Method1: Standard \n\t* Method2: Stable\n* Insertion Sort\n\t* Method1: Iterative\n\t* Method2: Recursive\n* Selection Sort\n\t* Method1: Standard\n\t* Method2: Standard using inbuilt\n* Bubble Sort\n* Quick Sort\n\t* Method1: Standard\n\t* Method2: Randomised\n* Merge Sort\n\t* Method1: Outplace Merging\n\t* Method2: Inplace Merging\n* Generalised Radix Sort\n\t* Method1: Using MinVal\n\t* Method2: Using Partitioning\n* Generalised Counting Sort\n* Heap Sort\n* Bucket Sort\n\n##### STL\n\n1. Method1: Standard (Accepted) [T(n) = O(n * lgn)]\n\n```\nvoid stlSort(vector<int>& nums) {\n\tsort(nums.begin(), nums.end());\n}\n```\n\n2. Method2: Stable (Accepted) [T(n) = O(n * lgn)]\n```\nvoid stableStlSort(vector<int>& nums) {\n\tstable_sort(nums.begin(), nums.end());\n}\n```\n\n##### Insertion Sort\n\n1. Method1: Iterative (TLE) [T(n) = O(n^2)]\n\n```\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}\n```\n\n2. Method2: Recursive (TLE) [T(n) = O(n^2)]\n\n```\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}\n```\n\n##### Selection Sort\n\n1. Method1: Standard (TLE) [T(n) = Theta(n^2)]\n\n```\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}\n```\n\n2. Method2: Standard using inbuilt (TLE) [T(n) = Theta(n^2)]\n\n```\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}\n```\n\n##### Bubble Sort (TLE)  [T(n) = Theta(n^2)]\n\n```\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}\n```\n\n##### Quick Sort\n\n1. Method1: Standard (TLE)  [T(n) = O(n^2)]\n\n```\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}\n```\n\n2. Method2: Randomised (TLE)  [T(n) = O(n * lgn) on avg. but O(n^2) in worst case]\n\n```\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}\n```\n\n##### Merge Sort\n\n1. Method1: Outplace Merging (Accepted) [T(n) = O(n * lgn)]\n\n```\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}\n```\n\n2. Method2: Inplace Merging (TLE) [T(n) = O(n^2)]\n\n```\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}\n```\n\n##### Generalised Couting Sort (Accepted) [T(n) = Theta(max(n, m)) where m = max(Arr)]\n\n```\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\t// int freqSize = maxVal - minVal + 1 is enough i.e its also correct\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}\n```\n\n##### Generalised Radix Sort \n\n1. Method1: Using MinVal (Accepted)  [T(n) = Theta(n)]\n\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}\n```\n\n2. Method2: Using Partitioning (Accepted)  [T(n) = Theta(n)]\n\n\tIdea 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.\n\tNote 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\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}\n```\n\n##### Heap Sort (Accepted) [T(n) = O(n * lgn)]\n\n```\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}\n```\n\n##### Bucket Sort\n\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\n##### Among above, Counting Sort was fastest in Leetcode OJ.\n\n**IMP:** You can also bookmark/ subscribe to this post so as to revise above Sorting Algorithms whenvever you need to. \n\n**NOTE:** \n*If you find this post helpful then please **upvote**. It keeps me **motivated** to post such helpful solutions. Thanks!*\n\n**PS:**\nI have also written posts on Kadane\'s Algorithm and Follow up Questions [C++] in a cleaner way [here](https://leetcode.com/problems/maximum-subarray/discuss/1470547/C++-Easy-and-Clean-Solution-or-Fastest:-0ms-or-All-Methods-or-Follow-Ups-or-Detailed-Explanation) on leetcode.\n*Do check it out/ bookmark (and upvote :)) to revise those concepts for the interview. Thanks!*\n\n
['Merge Sort', 'Bucket Sort', 'Radix Sort', 'Counting Sort', 'C++']