Merge Sort Algorithm

Merge Sort is a popular sorting algorithm that falls under the category of divide and conquer algorithms. It is known for its efficiency and stability, making it a preferred choice for sorting data in various programming scenarios. In this article, we will explore Merge Sort in Java, providing a detailed explanation and using a code example to demonstrate how it works.

Understanding Merge Sort

Merge Sort works on the principle of breaking down a larger problem into smaller subproblems and then merging the results of these subproblems to obtain the final sorted array. Here's a step-by-step explanation of the Merge Sort algorithm:

Divide: The unsorted array is divided into two equal halves until the subarrays become small enough to be sorted easily.
Conquer: The subarrays are recursively sorted using Merge Sort.
Merge: The sorted subarrays are merged to create larger sorted subarrays until the entire array is sorted.

Java Code

 class MergeSort{

        public static int[] mergeSort(int[] a){
            mergeSortt(a);
            return a;
        }
    
        public static void mergeSortt(int[] a){
            if(a.length < 2) { return ;}
    
            int n = a.length; 
            int middle = n / 2;  
            int[] left = new int[middle];      
            int[] right = new int[n - middle];
    
            for(int i = 0; i<= middle -1 ; i++){
                left[i] = a[i];
            }
    
            for(int j = middle ; j< n; j++){
                right[j-middle] = a[j];
            }
    
            mergeSortt(left);
            mergeSortt(right);
            merge(left, right, a);
        }
    
        public static void merge(int[] left, int[] right, int[] a){
            int l = left.length;
            int r = right.length;
            int i = 0;
            int j = 0;
            int k = 0;
    
            while( i < l && j < r){
                if(left[i] < right[j]){
                    a[k] = left[i];
                    i = i+1;
                }else{
                    a[k] = right[j];
                    j = j+1;
                }
    
                k =k+1;
            }
    
            while( i < l){
                a[k] = left[i];
                i = i+1;
                k = k+1;
            }
    
            while( j < r){
                a[k] = right[j];
                j = j+1;
                k = k+1;
            }
        }
    
        public static void main(String args[]){
            MergeSort m = new MergeSort();
    
            int[] arr = {2,15,27,5,8,45,36,18,26,41,49,10};
             System.out.print("Original array: ");
            for(Integer i : arr){
                System.out.print(i + "  ");
            }
    
            System.out.println();
            System.out.println("- - - - - - - - - - - - - - - - - - - - - - - - - - - -");
            
            int[] res = m.mergeSort(arr);
            System.out.print("Sorted array: ");
            for(Integer i : res){
                System.out.print(i + "  ");
            }
        }
  }

Output

Original array: 2 15 27 5 8 45 36 18 26 41 49 10 

- - - - - - - - - - - - - - - - - - - - - - - - - - - - 

Sorted array: 2 5 8 10 15 18 26 27 36 41 45 49

The original unsorted array is sorted in ascending order using the Merge Sort algorithm, producing the sorted result as expected.

Explanation of the Code

The mergeSort method is the entry point for the Merge Sort algorithm. It calls the private method mergeSortt, which is responsible for sorting the array.
In the mergeSortt method, the array is divided into two subarrays, left and right, using the middle index.
The mergeSortt method is then recursively called on the left and right subarrays.
Finally, the merge method is used to merge the sorted left and right subarrays back into the original array a.
The main method demonstrates the sorting process with an example array.

Time and space complexities

Time Complexity: Merge Sort is known for its consistent and efficient time complexity.

Best Case: O(n log n) - Merge Sort always divides the array into two halves and recursively sorts them, resulting in a time complexity of O(n log n) in the best case as well as in the average case.
Worst Case: O(n log n) - Merge Sort consistently performs with a time complexity of O(n log n) even in the worst-case scenario. This makes it suitable for large datasets.
Average Case: O(n log n) - Merge Sort's average-case time complexity is also O(n log n), which is better than many other sorting algorithms.

Space Complexity: Merge Sort has a space complexity of O(n).

Merge Sort requires additional space to store temporary subarrays during the merging process. In the worst case, this auxiliary space can be equal to the size of the input array, resulting in a space complexity of O(n).
While this additional space usage may seem like a drawback, Merge Sort's stability and consistent time complexity make it a preferred choice for sorting when memory is not a critical concern.

Summary

Merge Sort is highly efficient in terms of time complexity, and its space complexity is reasonable for most practical applications. Its stable performance across different scenarios makes it a reliable sorting algorithm for a wide range of use cases.

Dislike

Thanks for feedback.