# Merge Sort in Java

## Merge Sort in Java Programming Language

Merge Sort is a Divide & Conquer principle based algorithm, like  its cousin Quick  Sort. The main idea of merge sort is to divide large data-sets into smaller sets of data, and then solve them. Merge Sort is a recursive algorithm, it divides the given array into smaller half’s and then calls itself repeatedly to solve them. ## Steps for Merge Sort in Java

• The merge() is used for solving the sub-lists.
• The sub-lists are further divided into sub-parts, until they contain a single element.
• Then the sub-lists are combined together in the desired order.
• The time complexity of the merge sort is O(n log n) for best and worst case, and it is O(n) for the worst case.

While combining two sub-lists the first element of the list is taken into consideration, according to which all the sub-lists are combined together. For example if we are sorting in the ascending order, then the element with the smaller value becomes the new element of the sorted list, and this procedure continues until all the sub-lists are emptied, and we obtain a final list with all the entered elements in the sorted form ## Implementation of Merge Sort in JAVA ## JAVA Code for Merge Sort

```//Java Program for Merge Sorting
public class Main {
public static void display(int[] arr, int size)   //this function display the array
{
for(int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

public static void main(String[] args)   // main function of the program
{
int[] a = {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
int i;

int size = (int)a.length;
display(a, size);

mergeSort(a, 0, size - 1);
display(a, size);
}

static void mergeSort(int[] a, int strt, int end) //this function apply merging and sorting in the array
{
int mid;
if(strt < end)
{
mid = (strt + end) / 2;

mergeSort(a, strt, mid);
mergeSort(a, mid + 1, end);
merge(a, strt, mid, end);
}
}

static void merge(int[] a, int strt, int mid, int end)  //after sorting this function merge the array
{
int i = strt, j = mid + 1, p, index = strt;
int[] temp = new int;

while(i <= mid && j <= end) {
if(a[i] < a[j]) { temp[index] = a[i]; i = i + 1; } else { temp[index] = a[j]; j = j + 1; } index++; } if(i > mid) {
while(j <= end) {
temp[index] = a[j];
index++;
j++;
}
} else {
while(i <= mid) {
temp[index] = a[i];
index++;
i++;
}
}
p = strt;
while(p < index) {
a[p] = temp[p];
p++;
}
}
}```
```Output:
Input array - 11 9 6 19 33 64 15 75 67 88
Output array - 6 9 11 15 19 33 64 67 75 88
```

## Merge Sort Analysis

• Merge sort is quick algorithm and does sorting in only O(n log n) time
• However, it comes with a cost, which is extra space complexity which is too high in comparison to others which is o(n)
• While, one good thing is there that for all cases, the time complexity remains the same i.e. average, best, worst  