Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm.
In Merge Sort we basically Divide the Complete Array/List into Smaller Elements and then Sort them using the Conquer Technique. In simple terms, we can say that the process of merge sort is to divide the array into two halves, sort each half, and then merge the sorted halves back together. This process is repeated until the entire array is sorted.
Applications of Merge Sort:
Sorting large datasets
External sorting (when the dataset is too large to fit in memory)
Inversion counting (counting the number of inversions in an array)
Finding the median of an array
Complexity Analysis of Merge Sort:
Time Complexity:
Best Case: O(n log n), When the array is already sorted or nearly sorted.
Average Case: O(n log n), When the array is randomly ordered.
Worst Case: O(n log n), When the array is sorted in reverse order.
Space Complexity: O(n), Additional space is required for the temporary array used during merging.
#mergesort #dsalgo #dsa #java