mergesort.java

package test;

public class MergeSort {
	 

	  

	  private static void mergesort(int[] arr, int n) {
		  int mid;
		  int[] left;
		  int[] right;
		  if(n<2 ){return;}
		  mid = n/2;
		  
		  left = new int[mid];
		  right = new int[n-mid];
		  
		  for(int i=0;i<mid;i++){
			  left[i]=arr[i];
			  
		  }
		  for(int i=mid;i<n;i++){
			  right[i-mid]=arr[i];
			  
		  }
		  
		  mergesort(left,mid);
		  mergesort(right,n-mid);
		  merge(arr,left,mid,right,n-mid);
	    
	  }


	


	private static void merge(int[] arr, int[] left, int leftcount, int[] right, int rightcount) {
		// TODO Auto-generated method stub
		int i,j,k;
		
		i=0;j=0;k=0;
		
		while(i<leftcount && j<rightcount){
			if(left[i] <right[j]){
				arr[k]=left[i];
				k++;
				i++;
			}
			else{
				arr[k]=right[j];
				k++;
				j++;
				
			}
		}
		
		//copy what left if any
		while(i<leftcount){
			arr[k]=left[i];
			k++;
			i++;
		}
		//copy whats left if any
		while(j<rightcount){
			arr[k]=right[j];
			k++;
			j++;
		}
		
	}





	public static void main(String[]args){
		
		int[] arr = {2,4,1,7,3};
		for(int i = 0;i<arr.length;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		mergesort(arr,arr.length);
		for(int i = 0;i<arr.length;i++){
			System.out.println(arr[i] +" ");
		}
		
	}

	

}

i think we should do it better what better
in mergesort function u allocating space again n again i not want it i want a neat and clean code in mergesort method like

void mergesort(int arr[], int low, int high)
{
if(high > low)
{
int mid = low + (high - low)/2;
mergesort(arr, low,mid);
mergesort(arr,mid+1,high);
//call merge now
merge(arr,low,mid+1,high);
}
}

void merge(int arr[], int low, int mid, int high)
{
int s = (high - low + 1);
int *temp = new int[s];

 int i = low;
 int j = mid;

int k = 0;
while(i < mid && j <= high)
{
if(arr[i] < arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while(i < mid)
{
temp[k++] = arr[i++];
}
while(j <= high)
{
temp[k++] = arr[j++];
}

//now copy temp to arr
for(int i = 0; i < k; i++)
{
arr[low++] = temp[i];
}
}

Time complexity nlogn in best case avg case and worst case all r same here
Space complexity is O(n) that is temp array we allocated in merge method in worst case it become same size as array.