SORTING USING MERGE SORT ( C++ ) :)
Intuition\n Describe your first thoughts on how to solve this problem. \nin the Given Problem , We have to sort an array.\nTo Sort an array these are the most c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nin the Given Problem , We have to sort an array.\nTo Sort an array these are the most common algorithms : \n\n(1) Bubble Sort\n--------------------------------------------------------------\n- Approach : switches neighbouring parts frequently if the wrong order is given. The fundamental principle of Bubble Sort is to iteratively scan the array, compare nearby members, and swap out any that are out of order. Up till the full array is sorted, this procedure is repeated.\n- Time Complexity : O(n^2).\n- Space Complexty : O(1).\n\n(2) Selection Sort \n---------------------------------------------------------------\n- Approach : finding the minimum element from the unsorted part of the array and putting it at the beginning of the sorted part.\n- Time Complexity : O(n^2).\n- Space Complexity : O(1).\n\n(3) Quick Sort \n--------------------------------------------------------------------\n- Approach : divide-and-conquer approach to sort an array. The basic idea of Quick Sort is to divide the array into two smaller sub-arrays around a pivot element, and recursively sort these sub-arrays until the entire array is sorted.\n- Time Complexity :\n(i) Best and Average Case : O(nlogn).\n(ii) Worst Case : O(n^2).\n(iii) Space Complexty : O(n).\n\nThese are the most common sorting algorithms; however, we may also sort an array whose time complexity is "O(nlogn)" directly using the C++ STL "sort()" function.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIn the Given Problems , I use Merge Sort Algorithm to Sort an array which uses Divide and Conquer Approach :) \n\nMerge Sort : This algorithms works by dividing an array into smaller subarray , sorting each subarray and then merging the sorted subarray back together to form the final sorted array.\n\n- Pseudo Code\n(1) Declaring the variables "low" and "high," which serve as the array\'s beginning and ending points where low=0 and high=len(array)-1.\n(2) Calculate mid using "(low+high)/2" or "low+(high-low)/2".\n(3) Call the "MergeSort()" function on the part (low,mid) and (mid+1,high).\n(4) The above Call will continue till "low<high" is satisfied.\n(5) Finally Call "Merge" function to merge thse two halves.\n\n# Complexity\n- Time complexity: O(nlogn) { Best , Average and Worst Case }.\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 {\npublic:\n\n    void Merge(vector<int>& arr,int left,int mid,int right){\n\n        if(left>=right){\n            return;\n        }\n\n        int len=right-left+1;\n        vector<int> temp(len,0);\n        int i=left;\n        int j=mid+1;\n        int k=0;\n\n        while(i<=mid && j<=right){\n\n            if(arr[i]<arr[j]){\n                temp[k++]=arr[i++];\n            }\n\n            else{\n                temp[k++]=arr[j++];\n            }\n        }\n\n        while(i<=mid){\n            temp[k++]=arr[i++];\n        }\n\n        while(j<=right){\n            temp[k++]=arr[j++];\n        }\n\n        for(k=0;k<len;k++){\n            arr[k+left]=temp[k];\n        }\n\n    }\n\n    void MergeSort(vector<int>& arr,int left,int right){\n\n        if(left>=right){\n            return;\n        }\n\n        int mid=(left+(right-left)/2);\n        MergeSort(arr,left,mid);\n        MergeSort(arr,mid+1,right);\n        Merge(arr,left,mid,right);\n\n    }\n\n    vector<int> sortArray(vector<int>& nums) {\n        // Using Merge Sort to Sort the array \n        // Time Complexity --> O(nlogn) \n        // Space Complexity --> O(n)\n        int left=0;\n        int right=nums.size()-1;\n        MergeSort(nums,left,right);\n        return nums;\n    }\n};\n```
['Sorting', 'Merge Sort', 'C++']