## Merge sort

Merge sort algorithm is a divide and conquers approach based algorithm, with time complexity of n log(n) order, quicksort. An input array passed to sort using merge sort is divided into two equal parts until they are divided into small enough arrays that can be sorted and merged. In Merge sort java program there are two methods merge(), and sort(). merge() method merges two sorted arrays into one sorted array. sort() method first divides the input array into the smallest arrays possible that can be merged and calls the merge method() to merge arrays in sorted order. sort() method is recursive in nature. Merge sort can be applied with the help of recursion very easily.

## Merge Sort Algorithm

//Input is an array of numbers and left and right bound to apply to sort within

merge_Sort(arr[], left, right)

If right > left
1. Find the middle point to divide the array into two halves:
Middle element mid = (left+right)/2
2. Call merge_Sort for left half:
Call mergeSort(arr, left, mid)
3. Call merge_Sort for right half:
Call mergeSort(arr, mid, right)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, left, mid, right)

// merge is another method to merge two sorted arrays Merge Sort Algorithm(Sequence of execution)

## Merge Sort Program

public class MergeSortExample {
//merge sort
void merge(int arr[],int left,int mid,int right)
{
int ls=mid-left+1;
int rs=right-mid;
//create arrays
int left_arr[]=new int[ls];
int right_arr[]=new int[rs];
//copy
for(int i=0;i<ls;i++)
{
left_arr[i]=arr[left+i];
}
for(int j=0;j<rs;j++)
{
right_arr[j]=arr[mid+1+j];
}
//merge
int i=0;
int j=0;
int k=left;
while(i<ls && j<rs)
{
if(left_arr[i]<right_arr[j])
{
arr[k]=left_arr[i];
i++;
}
else
{
arr[k]=right_arr[j];
j++;
}
k++;
}
//merge remaining
while(i<ls)
{
arr[k]=left_arr[i];
i++;
k++;
}
while(j<rs)
{
arr[k]=right_arr[j];
j++;
k++;
}
//merge complete
}
//create sort method
void sort(int arr[],int l,int r)
{
if(r>l)
{
int mid=(r+l)/2;
sort(arr,l,mid);
sort(arr,mid+1,r);
merge(arr, l, mid, r);
}
}
public static void main(String[] args) {
//test
int arr[]= {7,1,13,15,16,45,12,6,11,33};
System.out.println("Array before sorting");
for(int i:arr)
System.out.print(i+"\t");
System.out.print();
MergeSortExample mse=new MergeSortExample();
mse.sort(arr, 0, arr.length-1);
System.out.println("Array after sorting");
for(int i:arr)
System.out.print(i+"\t");
}
}
Output:
Array before sorting
7     1     13    15    16    45    12    6     11    33
Array after sorting
1     6     7     11    12    13    15    16    33    45   Out