:::section{.main}

Merge Sort program in java is one of the most respected sorting algorithms, with a worst-case time complexity of O(nlogn). It works on the divide and conquer algorithm. It operates on the recursive division of the problem into subproblems, which are then combined to produce the final output (Sorted elements). The algorithm is based on the recursion approach but can also be implemented iteratively.

:::
:::section{.main}

Merge Sort Algorithm

Merge Sort is a well-known and successful sorting approach that uses the divide and conquer algorithm to divide a problem into many sub-problems. Let's see its algorithm and how it works:

• The array is recursively split into halves until each contains only one element.
• A merge() function combines two sorted sub-arrays into one.
• The process continues until the list is indivisible (each part has one element).
• The merging step starts with combining one-element lists, then progresses to two-element lists, and so forth, until the entire array is sorted.

:::

:::section{.main}

Java Program for Merge Sort

// merge sort program in java

public class Main { 
 
 public static void main(String[] args) { 
  int a[]= {91,52,83,23,62,15}; 
  int n=a.length; 
   
  //calling the function to sort the array 
  mergesort(a,0,n-1); 
  for(int e:a) 
   System.out.print(e+" "); 
 
 } 
  
 static void mergesort(int a[],int l,int r) { 
   
  if(l<r) { 
   int mid = l + (r-l)/2; 
    
   //sorting the left half 
   mergesort(a,l,mid); 
    
   //sorting the right half 
   mergesort(a,mid+1,r); 
    
   //merging both the halves 
   merge(a,l,mid,r); 
  } 
 } 
 
 private static void merge(int[] a, int l, int mid, int r) { 
  int a1[] = new int[mid-l+1]; 
  int a2[] = new int[r-mid]; 
   
  /* 
    Populating the left  
    range elements in the  
    a1 array. 
  */ 
  for(int i=l;i<=mid;i++){ 
   a1[i-l] = a[i]; 
  } 
   
  /* 
    Populating the right  
    range elements in the  
    a1 array. 
  */ 
  for(int i=mid+1;i<=r;i++){ 
   a2[i-mid-1] = a[i]; 
  } 
   
  int i = 0,j = 0,k = l; 
   
  //merging the elements of both the ranges. 
  while(i<a1.length && j<a2.length) { 
   if(a1[i]<=a2[j]) a[k++] = a1[i++]; 
   else a[k++] = a2[j++]; 
  } 
   
  //checking if any of the elements are left. 
  while(i<a1.length) a[k++] = a1[i++]; 
  while(j<a2.length) a[k++] = a2[j++]; 
 } 
}

Output:

Complexity Analysis

• Time Complexity: O(nlogn)
• Auxiliary Space: O(n)

In the example, we start with an unsorted array. Using the merge sort program in Java, we recursively break it down into smaller parts until each part is sorted individually. Then, we merge these sorted parts in ascending order to get the final sorted array. To learn more about merge sort complexity analysis, visit Merge Sort Algorithm.
:::

:::section{.main}

Advantages of Merge Sort

• Merge sort maintains the relative order of equal elements, ensuring stability.
• Its worst-case time complexity of O(NlogN) guarantees efficient performance, even with large datasets.
• The algorithm is naturally parallelizable, seamlessly utilising multiple processors or threads.
  :::

:::section{.summary}

Conclusion

• Merge sort program in java is a divide-and-conquer algorithm that calls itself recursively on halved pieces of the original collection.
• Merge Sort is an "out-of-place" sorting method. This means it needs more capacity to store the components it's sorting.
• Despite being one of the fastest and most efficient sorting algorithms, with an average time complexity of O(nlogn), it ranks with Quicksort, Timsort, and Heapsort.

:::