✅Easy Merge Sort Algorithm with Video Explanation
Video Explanation\nhttps://youtu.be/lsrEitj-fO8?si=5un2qApRDftE0IyW\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is t
# Video Explanation\nhttps://youtu.be/lsrEitj-fO8?si=5un2qApRDftE0IyW\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to sort an array of integers, and we are using the merge sort algorithm to achieve this. Merge sort is a classic divide-and-conquer algorithm that splits the array into halves, sorts each half recursively, and then merges the sorted halves back together.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Divide: Split the array into two halves by finding the middle index.\n2. Conquer: Recursively sort each half of the array.\n3. Combine: Merge the two sorted halves into a single sorted array.\n- The merge operation involves comparing elements from each half and arranging them in the correct order to form a sorted array.\n# Complexity\n- Time complexity:$$O(n*log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n\n    void merge(vector<int>& nums, int low, int mid, int high) {\n        vector<int> temp;\n        int left = low;\n        int right = mid + 1;\n        while (left <= mid && right <= high){\n            if(nums[left]<=nums[right]){\n                temp.push_back(nums[left++]);\n            }else{\n                temp.push_back(nums[right++]);\n            }\n        }\n        while(left<=mid){\n            temp.push_back(nums[left++]);\n        }\n        while(right<=high){\n            temp.push_back(nums[right++]);\n        }\n        for(int i=low;i<=high;i++){\n            nums[i]=temp[i-low];\n        }\n    }\n    void mergeSort(vector<int>& nums, int low, int high) {\n        if (low == high)\n            return;\n        int mid = (low + high) / 2;\n        mergeSort(nums, low, mid);\n        mergeSort(nums, mid + 1, high);\n        merge(nums, low, mid, high);\n    }\n\npublic:\n    vector<int> sortArray(vector<int>& nums) {\n        mergeSort(nums, 0, nums.size() - 1);\n        return nums;\n    }\n};\n```
['Array', 'Divide and Conquer', 'Sorting', 'Heap (Priority Queue)', 'Merge Sort', 'Bucket Sort', 'C++']