MergeSort Algorithm in Java

Mergesort algorithm is a divide and conquer algorithm. Its not efficient as Quicksort algorithm but in some cases Mergesort is better than Quicksort. For example its a linked list then Quicksort is costly since in a linkedlist accessing random elements is costly , since in Quicksort elements to be accessed randomly.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n log n)
Best Case Performance	O (n log n)
Average Case Performance	O(n log n)
Worst Case space Complexity		O (n)

	import java.io.*;
	import java.util.*;
	public class MergeSortAlgo{
	static int arr[] = { 11,34,55,67,23,64,78,34,12,84,33,5,5};
	private void MergeSort(int [] arr)
	{
	System.out.println("Split array " + Arrays.toString(arr));
	if(arr.length > 1)
	{
	int [] leftpart;
	int [] rightpart;
	int mid = arr.length / 2;
	if(arr.length%2 == 0)
	{
	leftpart = new int[mid];
	rightpart = new int[mid];
	System.arraycopy(arr, 0, leftpart, 0, mid);
	System.arraycopy(arr, mid, rightpart, 0, mid);
	}
	else
	{
	leftpart = new int[mid+1];
	rightpart = new int[mid];
	System.arraycopy(arr, 0, leftpart, 0, mid+1);
	System.arraycopy(arr, mid+1, rightpart, 0, mid);
	}
	MergeSort(leftpart);
	MergeSort(rightpart);
	int i=0,j=0,k=0;
	while ((i<leftpart.length) && (j<rightpart.length))
	{
	if(leftpart[i] < rightpart[j])
	{
	arr[k] = leftpart[i];
	i++;
	}
	else
	{
	arr[k] = rightpart[j];
	j++;
	}
	k++;
	}
	while(i < leftpart.length)
	{
	arr[k] = leftpart[i];
	i++;
	k++;
	}
	while(j < rightpart.length)
	{
	arr[k] = rightpart[j];
	j++;
	k++;
	}
	}
	System.out.println("Mergerd array " + Arrays.toString(arr));
	}
	public static void main(String []args)
	{
	System.out.println("Unsorted array " + Arrays.toString(arr));
	MergeSortAlgo obj = new MergeSortAlgo();
	obj.MergeSort(arr);
	System.out.println("Sorted array " + Arrays.toString(arr));
	}
	}

view raw MergeSortAlgo.java hosted with ❤ by GitHub