This tutorial shows how to write Merge sort program in Java. Merge sort is termed as a "*divide and conquer algorithm*"
and it is considered to be more efficient than the simple sort algorithms like selection sort and insertion sort.

### Merge sort algorithm

The algorithm for merge sort is based on the process of merging where two sorted arrays are merged to form a large sorted array. To merge the smaller arrays first you do need to divide your array into smaller arrays too so effectively Merge sort is a two step process.

- Divide the input array into two halves this process is carried out recursively until you get sub-arrays with only one element which is the base case for the recursive division. These sub-arrays of one element each are considered as sorted arrays.
- In this step these smaller arrays are sorted and merged recursively until you again get the larger sorted array. Merging process starts from bottom where a pair of single element sub-arrays are sorted and merged to create an array of two elements. Then a pair of such sorted sub-arrays of two elements are merged to create a sorted array of four elements and so on.

Following image shows the sub-division process for an array {43, 39, 54, 61, 81, 55, 92, 7}

At this point base case is encountered which starts the merging process that is explained using the following image.

### Merge Sort Java program

public class MergeSort { public static void main(String[] args) { int[] arr = {43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10}; System.out.println("Original array- " + Arrays.toString(arr)); MergeSort ms = new MergeSort(); ms.mergeSortRecursive(arr, 0, arr.length-1); System.out.println("Sorted array after merge sorting- " + Arrays.toString(arr)); } private void mergeSortRecursive(int[] arr, int start, int end){ //base case if (start == end){ return; }else{ // Middle point of the array int middle = (start + end)/2; // divide array into two parts using middle point mergeSortRecursive(arr, start, middle); mergeSortRecursive(arr, middle+1, end); // call merge process merge(arr, start, middle, end); } } private void merge(int[] arr, int start, int middle, int end){ // Create two temp arrays for two halves int temArray1Length = middle - start + 1; int temArray2Length = end - middle; int[] temp1 = new int[temArray1Length]; int[] temp2 = new int[temArray2Length]; for(int i = 0; i < temArray1Length; i++){ temp1[i] = arr[start + i]; } for(int j = 0; j < temArray2Length; j++){ temp2[j] = arr[middle + 1 + j]; } int i =0; int j = 0; // merging process, merge two temp arrays put the // sorted elements in original array while((i < temArray1Length) && (j < temArray2Length)){ if(temp1[i] < temp2[j]){ arr[start] = temp1[i++]; }else{ arr[start] = temp2[j++]; } start++; } // Add left over elements from temp arrays while(i < temArray1Length){ arr[start++] = temp1[i++]; } while(j < temArray2Length){ arr[start++] = temp2[j++]; } } }

__Output__Original array- [43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10] Sorted array after merge sorting- [0, 7, 10, 15, 39, 43, 54, 55, 61, 81, 92, 112]

### Merge sort time and space complexity

Time complexity of merge sort is **O(n*logn)** where logn is the complexity of sub-dividing the array and
n is the complexity for merging n elements at each level.

Space complexity of merge sort is **O(n)** as extra space for temp array is required which is equal to the
length of the input array.

That's all for the topic **Merge sort Java Program**. If something is missing or you have something to share
about the topic please write a comment.

**You may also like**

## No comments:

## Post a Comment