Today in this post you will learn merge sort java.

#### Merge sort

Merge sort is divide and conquer algorithm. Merge sort is comparison based sorting algorithm which sorts array in ascending order.

Also read – bubble sort java program

In merge sort, given array is divided into two smaller portions. To divide a collection, mergesort take the middle of collection and split into two smaller lists.

These two smaller portions are again recursively splitted till they are broken into single element. Let’s learn merge sort with an example.

So let’s say we want to sort a small list of integers 20, 40, 30 and 10.

One way to sort them would be to recursively divide the list into two smaller lists. 20, 40 and 30, 10.

Now 20 and 40 is already sorted, but 30 and 10 have to swap places. After swapping we have 20, 40, 10 and 30.

The leftmost number is the smallest number in above two smaller list. So we compare 20 and 10. 10 is smaller so we will add 10 to the main list first and then we compare the remaining integers.

Also read – how to sort hashmap by values in java

20 is the smaller so we add 20 to the main list. Then we compare 30 and 40, 30 is the smaller number so we add 30 to main list.

Now all we have left is 40. So we add that too to the main list. Now we have a sorted list of four integers. That in a nutshell is how merge sort works.

Below is the java program for merge sort,

public class JavaMergeSort { void sorting(int num[], int left, int main, int right) { // finding size of two sub arrays int list1 = main - left + 1; int list2 = right - main; // creating temporary array int L[] = new int[list1]; int R[] = new int[list2]; // copying data to temporary array for(int a = 0; a < list1; ++a) L[a] = num[left + a]; for(int b = 0; b < list2; ++b) R[b] = num[main + 1+ b]; // existing index of first and second sub array int p = 0, q = 0; // existing index of merged sub array int r = left; while(p < list1 && q < list2) { if(L[p] <= R[q]) { num[r] = L[p]; p++; } else { num[r] = R[q]; q++; } r++; } // copying remaining elements of L[] array while(p < list1) { num[r] = L[p]; p++; r++; } // copying remaining elements of R[] array while(q < list2) { num[r] = R[q]; q++; r++; } } // function that sorts void sort(int arrNum[], int l, int r) { if(l < r) { // finding middle point int m = (l + r) / 2; // sorting first and second list sort(arrNum, l, m); sort(arrNum , m+1, r); // merging sorted list sorting(arrNum, l, m, r); } } // display array static void displayArray(int arr[]) { int number = arr.length; for(int a = 0; a < number; ++a) System.out.print(arr[a] + " "); System.out.println(); } public static void main(String[] args) { int arrNumbers[] = {33, 00, 55, 11, 22, 44}; System.out.println("Before sorting - ");displayArray(arrNumbers); JavaMergeSort obj = new JavaMergeSort(); obj.sort(arrNumbers, 0, arrNumbers.length - 1); System.out.println("\nAfter sorting - ");displayArray(arrNumbers); } }

**Output:**

Before sorting –

33 00 55 11 22 44

After sorting –

0 11 22 33 44 55

**Time and space complexity of merge sort**

Time complexity of merge sort is **O(n log n)** can be expressed as recurrence relation,

T(n) = 2T(n/2) + O(n)

**Space :** O(n)