C++ | Quick sort | Merge sort | Visual explanation
Quick sort\nThis works just like how a preorder tree  traversal does. Here I use Lomuto partition scheme.\n1. For each recursion call, get one element sorted as
**Quick sort**\nThis works just like how a preorder tree  traversal does. Here I use Lomuto partition scheme.\n1. For each recursion call, get one element sorted as pivot. \n2. Recurse on the left part and the right part\n\n![image](https://assets.leetcode.com/users/images/9acbc10c-aa20-43f3-987e-9d99f0b202dd_1660923159.2145824.jpeg)\n\n![image](https://assets.leetcode.com/users/images/d5986c92-ae7c-4db3-ba91-f5aecefb1d2b_1660923159.3761039.jpeg)\n\n\n**Code**\n```\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        QuicksortHelper(nums, 0, size(nums) - 1);\n        return nums;\n    }\nprivate:\n    int Partition(vector<int>& nums, int left, int right) {\n\t    // To avoid TLE, take the element in the middle as the pivot\n\t\t// Would be even better to use a random element\n        int mid = left + (right - left) / 2;\n        swap(nums[mid], nums[right]);\n\t\t\n        int pivot = nums[right];\n        int j = left;\n        for (int i = left; i < right; ++i) {\n            if (nums[i] < pivot) {\n                std::swap(nums[i], nums[j]);\n                ++j;\n            }\n        }\n        std::swap(nums[j], nums[right]);\n        return j;\n    }\n    \n    void QuicksortHelper(vector<int>& nums, int left, int right) {\n        if (left >= right) {\n            return;\n        }\n        int pivot_index = Partition(nums, left, right);\n        QuicksortHelper(nums, left, pivot_index - 1);\n        QuicksortHelper(nums, pivot_index + 1, right);\n    }\n};\n```\n\n\n\n**Merge sort**\nThis works like a postorder tree traversal.\n1. Keep dividing the array in half until only a single element is left.\n2. Start merging pairs of sorted arrays.\n\n![image](https://assets.leetcode.com/users/images/1bf92d85-869a-45bd-9741-86302337096f_1660923170.3856132.jpeg)\n\n![image](https://assets.leetcode.com/users/images/abdf53ac-7e9b-4144-a751-fc16b7272d34_1660923170.0152829.jpeg)\n\n**Code**\n```\nclass Solution {\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        MergesortHelper(nums, 0, size(nums) - 1);\n        return nums;\n    }\nprivate:\n    void MergeTwoSortedArray(vector<int>& nums, int left, int mid, int right) {\n        vector<int> sorted;\n        sorted.reserve(right - left + 1);\n        \n        int k = 0;\n        int i = left;\n        int j = mid + 1;\n        \n        while (i <= mid && j <= right) {\n            if (nums[i] < nums[j]) {\n                sorted[k++] = nums[i++];\n            } else {\n                sorted[k++] = nums[j++];\n            }\n        }\n        \n        while (i <= mid) {\n            sorted[k++] = nums[i++];\n        }\n        \n        while (j <= right) {\n            sorted[k++] = nums[j++];\n        }\n        \n        while (--k >= 0) {\n            nums[right--] = sorted[k];\n        }\n    }\n    \n    void MergesortHelper(vector<int>& nums, int left, int right) {\n        if (left == right) {\n            return;\n        }\n        int mid = left + (right - left) / 2;\n        MergesortHelper(nums, left, mid);\n        MergesortHelper(nums, mid + 1, right);\n        MergeTwoSortedArray(nums, left, mid, right);\n    }\n};\n```\n\nPlease let me know if anything could be improved. Happy coding!
['C', 'C++']