C++ -- Merge sort, Quick sort, Heap sort, Bubble sort, Insert sort, Selection sort.
\nclass Solution {\npublic:\n    /*\n    1. Bubble sort:\n    Worstcase time: O(n^2), Bestcase Time: O(n) -  list already sorted, Space: O(1)\n    */\n    vecto
```\nclass Solution {\npublic:\n    /*\n    1. Bubble sort:\n    Worstcase time: O(n^2), Bestcase Time: O(n) -  list already sorted, Space: O(1)\n    */\n    vector<int> bubbleSort(vector<int>& nums) {\n        for(int i=0;i<nums.size()-1;i++){\n            bool found = false;\n            for (int j=0;j<nums.size()-i-1;j++){\n                if (nums[j]>nums[j+1]){\n                    found = true;\n                    swap(nums[j],nums[j+1]);\n                }\n            }\n            if (!found)\n                return nums;\n        }\n        return nums;\n    }\n    \n\t\n    /*\n    2. Insertion sort: (Inserting ith element in the proper position)\n    Worstcase time: O(n^2), Bestcase Time: O(n) - list already sorted, Space: O(1)\n    */\n    vector<int> insertionSort(vector<int>& nums) {\n        for(int i=0;i<nums.size();i++){\n            int j = i;\n            while (j>0 && nums[j-1]>nums[j]){\n                swap(nums[j],nums[j-1]);\n                j--;\n            }\n        }\n        return nums;   \n    }\n\n\n    /*\n    3. Selection sort: (Select the  min/max value based on current element and swap it)\n    Worstcase time: O(n^2), Bestcase Time: O(n^2), Space: O(1)\n    */\n    vector<int> selectionSort(vector<int>& nums) {\n        for(int i=0;i<nums.size()-1;i++){\n            int minIndex = i;\n            for (int j=i+1;j<nums.size();j++){\n                if (nums[minIndex]>nums[j])\n                    minIndex = j;\n            }\n            swap(nums[i], nums[minIndex]);\n        }\n        return nums;\n    }\n\n\n    /*\n    4. Merge sort: (divide and concur)\n    Worstcase time: O(nlogn), Bestcase Time: O(nlogn), Space: O(n) (not considering recursion call stack space)\n    It is a divide and concure technique which \n    Divide: Break the given problem into sub-problems of same type.\n    Conquer: Recursively solve these sub-problems\n    Combine: Appropriately combine the answers\n    1. Base operation: find the mid elemet\n    2. Divide and  concure part: divide the array into two halves and recursively solve these sub-problems\n    3. Combine part: appropriately add sorted two halves arrays\n    T(n) = 0(1)(Finding mid index -- preprocessing) + 2T(n/2) + O(N) (merging - postprocessing)\n    T(n) = 2T(n/2) + O(n) --> O(nlong)\n    T(N) = aT(n/b) + f(n) -- >  logn(baseb) is the height and max no of leafs is a^heigh and total number a^(height+1)-1 (Here n is the length of the array)\n    According to master method:\n    T(N) = aT(n/b) + f(n)\n    T(n) = \u0398(nloga(baseb)) when f(n) has slower growth that n^loga(baseb)\n    T(n) = \u0398(nloga(baseb) log n) when f(n) has equal growth that n^loga(baseb)\n    T(n) = \u0398(f(n)) when f(n) has faster growth that n^loga(baseb) \n    */\n    void merge(vector<int>& nums, int low, int mid, int high) {\n        int leftLength = mid-low + 1;\n        int rightLength = high -mid; // high-(mid+1)+1\n        vector<int> leftList(nums.begin()+low, nums.begin()+mid+1);\n        vector<int> rightList(nums.begin()+mid+1, nums.begin()+high+1); \n        int i=0,j=0,cur=low;\n        while(i<leftLength && j<rightLength){\n            if (leftList[i]<rightList[j]){\n                nums[cur] = leftList[i];\n                i++;\n                cur++;\n            } else {\n                nums[cur] = rightList[j];\n                j++;\n                cur++;              \n            }   \n        }\n        while(i<leftLength){\n            nums[cur] = leftList[i];\n            i++;\n            cur++;\n        }\n         while(j<rightLength){\n            nums[cur] = rightList[j];\n            j++;\n            cur++;\n        }        \n    }\n    void mergeSortHelper(vector<int>& nums, int low, int high) {\n        if (low<high){\n            int mid = (high-low)/2 + low;\n            mergeSortHelper(nums, low, mid);\n            mergeSortHelper(nums, mid+1, high);\n            merge(nums, low, mid, high);\n        }\n    }\n    vector<int> mergeSort(vector<int>& nums) {\n        mergeSortHelper(nums, 0, nums.size()-1);\n        return nums;\n    }\n\n\n    /*\n    5. Heapsort (Using heap)\n    Worstcase time: O(nlogn), Bestcase Time: O(n)(when all elements are same then heapify will not cost O(logn), it will be O(1)), Space: O(1) (not including recursive function stack space.)\n    */    \n    // heapify opertaion for max heap\n    void heapify(vector<int>& nums, int index, int size){\n        int lChildIndex = 2*index +1;\n        int rChildIndex = 2*index +2;\n        int nextIndex = index;\n        if (lChildIndex<size && nums[lChildIndex]>nums[nextIndex])\n            nextIndex = lChildIndex;\n        if (rChildIndex<size && nums[rChildIndex]>nums[nextIndex])\n            nextIndex = rChildIndex;\n        if (nextIndex != index){\n            swap(nums[index], nums[nextIndex]);\n            heapify(nums, nextIndex, size);\n        }\n    }\n    void heapSortHelper(vector<int>& nums){\n        // Make the array as max heap. Time complexity is O(n), it is not nlogn because height considered in each call is not the same and decreases.\n        for (int i=nums.size()/2;i>=0;i--){ \n            heapify(nums, i, nums.size());\n        }\n        // Swap 0th element with last, as 0 will be the max element and then heapify the 0th element by passing size as last-1. Time complexity is nlogn, and it will be n if all elements are same.\n        for (int i=nums.size()-1;i>=0;i--){\n            swap(nums[0], nums[i]);\n            heapify(nums, 0, i);\n        }\n    }\n    vector<int> heapSort(vector<int>& nums) {\n        heapSortHelper(nums);\n        return nums;\n    }\n\n\n    /*\n    6. Quick sort:\n    Worstcase time: O(n^2), Bestcase Time: O(nlogn), Ave: O(nlogn), Space: O(1)-- not including recursive function stack space.\n    Quicksort uses divide-and-conquer approach.\n    1. Base operation: find pivot element\n    2. Divide and concure art: divide the array into two halves and recursselvy quicksort the array\n    3. Combine part do nothing\n    best case and avg case when partition element is around middle and in that case\n    T(n) = O(n) + 2T((n-1)/2) + Nothing -- best case \n    T(n) = O(n) + T(9n/10)+ T(n/10) -- > O(n logn) -- averge case\n    Worstcase when partition element is around start and end every time -- revered sorted input list provided here:\n    T(n) = O(n) + T(n-1) + Nothing -- > O(n + n-1 + n-2 + .. ) --> O(n^2)\n    We can use randomized quicksort which gives worst case complexity as O(n logn) by picking pivot element randomly.  But it can not gurantee, complexity can go to O(n^2) here also.\n    */\n    \n    int partitionIndex(vector<int>& nums, int low, int high){\n        int index = low-1;\n        for (int j=low;j<=high;j++){\n            if (nums[j]<= nums[high]){\n                index++;\n                swap(nums[index], nums[j]);\n            }\n        }\n        return index;\n    }\n    void quickSortHelper(vector<int>& nums, int low, int high){\n        if (low<high){\n            int p = partitionIndex(nums, low, high);\n            quickSortHelper(nums, low, p-1);\n            quickSortHelper(nums, p+1, high);\n        }\n    }\n    vector<int> quickSort(vector<int>& nums) {\n        quickSortHelper(nums, 0, nums.size()-1);\n        return nums;\n    }\n    /*\n    Note considering high index for finding partition element gives O(n^2) time complexity in case list is sorted in reverse order. So to increase the probability of getting O(nlogn) complexity, randomized quick sort can be used. \n    int partitionIndex(vector<int>& nums, int low, int high){\n        int randIndex = low + rand()%(high-low+1);\n        swap(nums[randIndex], nums[high]);\n        int index = low-1;\n        for (int j=low;j<=high;j++){\n            if (nums[j]<= nums[high]){\n                index++;\n                swap(nums[index], nums[j]);\n            }\n        }\n        return index;\n    }\n    */\n    \n    vector<int> sortArray(vector<int>& nums) {\n        //bubbleSort(nums);\n        //insertionSort(nums);\n        //selectionSort(nums);\n        //heapSort(nums);\n        mergeSort(nums);\n        //quickSort(nums);\n        return nums;\n    }\n};\n```
[]