✅✅C++ ||  MERGE SORT | QUICKSORT | INSERTION SORT | HEAP SORT |BUBBLE SORT
Bubble sort\n\n\t// bubbleSort(nums);\n\tvoid bubbleSort(vector& nums){\n        for(int i = nums.size() - 1; i >= 0; i--)\n            for(int j = 0; j < i; j+
Bubble sort\n\n\t// bubbleSort(nums);\n\tvoid bubbleSort(vector<int>& nums){\n        for(int i = nums.size() - 1; i >= 0; i--)\n            for(int j = 0; j < i; j++)\n                if(nums[j] > nums[j + 1]) \n                    swap(nums[j], nums[j + 1]);\n    }\nInsertion sort\n\n\t// insertionSort(nums);\n\tvoid insertionSort(vector<int>& nums){\n        if(nums.size() == 0 || nums.size() == 1) return;\n        for(int i = 1; i < nums.size(); i++){\n            int tmp = nums[i];\n            int j = i - 1;\n            while(j >= 0 && nums[j] > tmp){\n                nums[j + 1] = nums[j];\n                j--;\n            }\n            nums[j + 1] = tmp;\n        }\n    }\nHeap sort\n\nIn terms of heapify stage:\n\nBottom up approach (beginning from bottom + sift down) O(n)\nTop down approach (beginning from top + sift up) O(nlogn)\nBeginning from top + sift down not working\nIn fact, "sift down" of a certain node x works properly only if both of its left subtree and right subtree (if any) already satisfy the heap property.\n\nFor zero-based arrays, for a certain node x:\n\nits parent floor( (x - 1) / 2 )\nits left child 2x + 1\nits right child 2x + 2\nThe index of the last non-leaf node of a n-sized heap is floor( n / 2 ) - 1.\n\n\tvoid siftDown(vector<int>& nums, int n, int i){\n        int biggest = i;\n        int l = 2 * i + 1;\n        int r = 2 * i + 2;\n        if(l < n && nums[biggest] < nums[l])\n            biggest = l;\n        if(r < n && nums[biggest] < nums[r])\n            biggest = r;\n        if(biggest != i){\n            swap(nums[i], nums[biggest]);\n            siftDown(nums, n, biggest);\n        }\n    }\n    \n\t// heapSort(nums);\n    void heapSort(vector<int>& nums){\n        // heapify stage (bottom up approach)\n        for(int i = nums.size() / 2 - 1; i >= 0; i--)\n            siftDown(nums, nums.size(), i);\n        // sorting stage\n        for(int i = nums.size() - 1; i > 0; i--){\n            swap(nums[0], nums[i]);\n            siftDown(nums, i, 0);\n        }\n    }\nMerge sort (recursive version)\n\n\tvoid merge(vector<int>& nums, int l, int m, int r){\n        vector<int> tmp(r - l + 1);\n        int i = l; // index for left subarray\n        int j = m + 1; // index for right subarray\n        int k = 0; // index for temporary array\n        while(i <= m && j <= r){\n            if(nums[i] <= nums[j]) tmp[k++] = nums[i++]; \n            else tmp[k++] = nums[j++];\n        }\n        while(i <= m) tmp[k++] = nums[i++];\n        while(j <= r) tmp[k++] = nums[j++]; \n        for(i = 0; i < k; i++) nums[l + i] = tmp[i];\n    }\n\t\n\t// mergeSort(nums, 0, nums.size() - 1);\n    void mergeSort(vector<int>& nums, int l, int r){\n        if(l >= r) return;\n        int m = l + (r - l) / 2; //middle index, same as (l+r)/2\n        mergeSort(nums, l, m);\n        mergeSort(nums, m + 1, r);\n        merge(nums, l, m, r);\n    }\nQuick sort (recursive version)\n\n\t// quickSort(nums, 0, nums.size() - 1);\n    void quickSort(vector<int>& nums, int l, int r){\n        if(l >= r) return;\n        int i = l; // cursor for final pivot location \n        for(int j = l; j <= r - 1; j++){ // nums[r] is chosen as the pivot\n            if(nums[j] <= nums[r]){\n                swap(nums[i], nums[j]);\n                i++; // smaller or equal elements go to the left of i \n            }\n        }\n        swap(nums[i], nums[r]); // after swap, the pivot is nums[i]\n        quickSort(nums, l, i - 1);\n        quickSort(nums, i + 1, r);\n    }\nThe utility function swap is defined as follows\n\n\tvoid swap(int& a, int& b){\n        int tmp = a;\n        a = b;\n        b = tmp;\n    }
['Sorting', 'Heap (Priority Queue)', 'Merge Sort']