## Thursday, 5 April 2018

### Implementation of merge sort in Java

In previous post, implemented the Selection Sort in JavaIn this post, we can implement the merge sort and also discuss the time complexity.

Merge Sort is a fast, recursive, stable sort algorithm which works by the divide and conquer principle. The algorithm has a complexity of O(n log (n)). Merge Sort is similar to Quick Sort(Will implement in the next post) the list of elements which should be sorted is divided into two lists. These lists are sorted independently and then combined. During the combination of the lists the elements are inserted (or merged) on the correct place in the list.

It involves the following steps,

• Divide the array into two (or more) sub arrays.
• Sort each sub array (Conquer).
• Merge them into one (in a smart way)
MergeSort.java,

```package com.test;

public class MergeSort {
private int[] arr;
private int[] temp;
private int length;
```
```        public static void main(String a[]){
int[] arr = {60,8,44,71,33,96,12,10,46};

System.out.println("Array before sorting:--");
for(int i=0;i < arr.length;i++){
System.out.println(arr[i]);
}

MergeSort mers = new MergeSort();
mers.sort(arr);

System.out.println("Array after sorting:--");
for(int i:arr){
System.out.println(i);
}
}
```
```        public void sort(int arr[]) {
this.arr = arr;
this.length = arr.length;
this.temp = new int[length];
MergeSortArr(0, length - 1);
}
```
```        private void MergeSortArr(int lowIndex, int highIndex) {
if (lowIndex < highIndex) {
int middle = lowIndex + (highIndex - lowIndex) / 2;
MergeSortArr(lowIndex, middle);
MergeSortArr(middle + 1, highIndex);
MergeSortArr1(lowIndex, middle, highIndex);
}
}
```
```        private void MergeSortArr1(int lowIndex, int middle, int highIndex) {
for (int i = lowIndex; i <= highIndex; i++) {
temp[i] = arr[i];
}
int i = lowIndex;
int j = middle + 1;
int k = lowIndex;
while (i <= middle && j <= highIndex) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= middle) {
arr[k] = temp[i];
k++;
i++;
}

}
}
```

Output:--
Array before sorting:--
60
8
44
71
33
96
12
10
46
Array after sorting:--
8
10
12
33
44
46
60
71