Merge Sort in Java

Merge sort works on the principle of divide and conquer.
Divide the list in 2 sub-lists, and repeat until there is only 1 element, a sub-list with single element is already sorted.
Now merge the sorted sub-lists to get a sorted list until there is only a single sorted list.

Algorithm:
1. MergeSort(Arr, p ,r)
2. if(p < r)
3.  q=[p+r/2];
4.  MergeSort(Arr, p,q);    //left sub array
5.  MergeSort(Arr, q+1,r);  // right sub array
6.  Merge(Arr, p , q, r);   //Merge, sorted sub arrays [takes O(n) ]

Following program implements Merge sort in java.

/**
 * @author Vikky.Agrawal
 *
 */
public class MergeSort {

 
 int[] arr;
 
 MergeSort(){
  arr=new int[] { 5, 3, 1, 2, 9, 8 };
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {

  MergeSort obj = new MergeSort();
  obj.operate();
 }
 
 
 public void operate(){
  System.out.println("Array before sortings: ");
  printArray();
  mergeSort(arr,0,5);

  System.out.println("Sorted array : ");
  printArray();
 }
 
 
 public void mergeSort(int[] arr, int p, int r){
  if(p<r){
   int q=(p+r)/2;
   mergeSort(arr, p, q);
   mergeSort(arr, q+1, r);
   merge(arr,p,q,r);
  }
 }
 
 public void merge(int[] arr, int p, int q, int r){
  
  int length=arr.length;
  int[] tempArray =new int[length];

  for (int i=0;i<length; i++) {
   tempArray[i]=arr[i];
  }
  
  int temp=p;
  int i=p,j=q+1;
  for(; i<=q && j<=r ; ){
   if(tempArray[i] < tempArray[j]){
    arr[temp++]=tempArray[i];
    i++;
   }else{
    arr[temp++]=tempArray[j];
    j++;
   }
  }
  
  while(i <= q){
   arr[temp++]=tempArray[i];
   i++;
  }
  
  while(j < r){
   arr[temp++]=tempArray[j];
   j++;
  }
 }
 

 public void printArray(){
  for (int a : arr) {
   System.out.print(a + " ");
  }
  System.out.println();
 }

}

Complexity analysis:
Since each problem is divided in 2 sub problems and then these sub problems merged.
Total time required will be T(n)= 2T(n/2)+O(n)
where O(n) is to merge sub problems.
Using Master theorem #case2 solution to above equation comes as O(n logn).

In worst case scenario Merge sort beats Quick sort which requires O(n^2)
worst case time.

For more analysis follow wikipedia: Merge_sort#Analysis
In the worst case, the number of comparisons merge sort makes is equal to or slightly smaller than (n logn - 2 logn + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n))