Data Structures - UnderStanding Merge Sort

Data structures is asked in every programming interview. Irrespective of the programming language, data structures and algorithm puzzles are asked in every programming interview.Sorting is one of the most common topic asked in data structures.
 Merge Sort  works on the concept of Divide and Conquer approach.But it doesn't divides the list into two halves. In merge sort the unsorted list is divided into N sublists, each having one element, because a list of one element is considered sorted.
Then, it repeatedly merge these sublists, to produce new sorted sublists, and at lasts one sorted list is produced. The merge() method is used for merging two halves. The merge(arr, l, r) is key process that assumes that l and r  are sorted and merges the two sorted sub-arrays into one arr.

import java.util.Arrays;

public class MergeSort {

 public static void main(String[] args) {

  int arr[] ={4,5,6,7,8,3,21,2,3,4,1,12,12,14,12,12,1,2,45,1,21,5,1};
  System.out.println(Arrays.toString(arr));  
   new MergeSort().sort(arr);
   System.out.println(Arrays.toString(arr));
 }



 public void sort(int arr[]){
  
if(arr.length>1){
 int mid=arr.length/2;
 int left[]=new int[mid];
 int []right = new int[arr.length-mid];
 
 for(int i=0;i<left.length;i++){
  left[i]=arr[i];
 }
 for(int i=mid;i<arr.length;i++){
  right[i-mid]=arr[i];
 }
 sort(right);
 sort(left);
 merge(arr, left, right);
 
}


 }


 public void merge(int arr[],int left[],int []right)
 {
  int l=0;
  int r=0;
  int count=0;
  while(l<left.length && r<right.length)
  {
   if(left[l]<right[r])
   {
    arr[count++]=left[l++]; 
   }
   else
    arr[count++]=right[r++];
  }
  while(l<left.length)
  {
   arr[count++]=left[l++];
  }
  while(r<right.length)
  {
   arr[count++]=right[r++]; 
  }
  System.out.println("End of Array:::"+Arrays.toString(arr));

 }



}

Time Complexity: Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + Theta(n)
The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is \Theta(nLogn). Time complexity of Merge Sort is Theta(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.
Auxiliary Space: O(n) Algorithmic Paradigm: Divide and Conquer Sorting In Place: No in a typical implementation  
Stable: Yes